状态转移公式递推公式是很重要但动规不仅仅只有递推公式。对于动态规划问题可以拆解为如下五步曲确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组01背包问题题目描述有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。每一件物品其实只有两个状态取或者不取所以可以使用回溯法搜索出所有的情况那么时间复杂度就是$o(2^n)$这里的n表示物品数量。所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化举一个例子背包最大重量为4。物品为重量价值物品0115物品1320物品2430问背包能背的物品最大价值是多少二维dp数组确定dp数组以及下标的含义对于背包问题有一种写法 是使用二维数组即dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。确定递推公式再回顾一下dp[i][j]]的含义从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。那么可以有两个方向推出来dp[i][j]不放物品i由dp[i - 1][j]推出即背包容量为j里面不放物品i的最大价值此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时物品i无法放进背包中所以背包内的价值依然和前面相同。)放物品i由dp[i - 1][j - weight[i]]推出dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值那么dp[i - 1][j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值所以递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);dp数组如何初始化关于初始化一定要和dp数组的定义吻合否则到递推公式的时候就会越来越乱。首先从dp[i][j]的定义出发如果背包容量j为0的话即dp[i][0]无论是选取哪些物品背包价值总和一定为0。如图在看其他情况。状态转移方程 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 可以看出i 是由 i-1 推导出来那么i为0的时候就一定要初始化。dp[0][j]即i为0存放编号0的物品的时候各个容量的背包所能存放的最大价值。那么很明显当 j weight[0]的时候dp[0][j] 应该是 0因为背包容量比编号0的物品重量还小。当j weight[0]时dp[0][j] 应该是value[0]因为背包容量放足够放编号0物品。代码初始化如下javafor (int j 0 ; j weight[0]; j) { // 当然这一步如果把dp数组预先初始化为0了这一步就可以省略但很多同学应该没有想清楚这一点。 dp[0][j] 0; } // 正序遍历 for (int j weight[0]; j bagweight; j) { dp[0][j] value[0]; }此时dp数组初始化情况如图所示dp[0][j] 和 dp[i][0] 都已经初始化了那么其他下标应该初始化多少呢其实从递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 可以看出dp[i][j] 是由左上方数值推导出来了那么 其他下标初始为什么数值都可以因为都会被覆盖。初始-1初始-2初始100都可以但只不过一开始就统一把dp数组统一初始为0更方便一些。如图确定遍历顺序在如下图中可以看出有两个遍历的维度物品与背包重量那么问题来了先遍历 物品还是先遍历背包重量呢其实都可以 但是先遍历物品更好理解。理解递归的本质和递推的方向。