代码随想录算法训练营第三十五天-动态规划-01背包（二维）

动规五部曲

• dp数组的含义，注意这是一个二维数组。dp[i][j]
  • 第一维度代表“从0到第i个物品，而且包括选或不选的情况，即这一维度代表物品编号
  • 第二维度代表代表背包容量
  • 合在一起的意思是当背包容量是j时，从0到i个物品中选择任意物品的最大价值
• 递推公式：两种选择
  • 第一是不选择物品i，则当前最大值就是要从前i - 1个物品且容量为j的最大值
  • 第二是选择当前物品i，则最大值是i物品的价值，加上背包可以放下i物品重量时量大容量的最大价值
  • 合并在一起写出来就是：dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
• 初始化数组
  • 增加一个什么物品都没有的行，可以列在所有物品行的最上面，这一行都可以上初始化为0
  • 把第一列，即容量为0的列，都可以初始化成0