本文来自对《代码随想录》的学习。
动态规划五部曲：
1.确定dp数组以及下标含义；
2.确定递推公式；
3.dp数组如何初始化；
4.确定遍历顺序；
5.举例推导dp数组。
动态规划如何debug？
最好的方式是把dp数组打印出来，看看究竟是不是按照自己的思路推导的；
写代码前一定要把状态转移在dp数组上的具体情况模拟一遍，确定最后推出的是想要的结果。
背包问题
01背包：有n件物品和一个最多能背重量为w的背包。第i件物品的重量是w[i]，得到的价值是v[i]。每件物品只能用一次，求解可以得到的最大总价值。
二维dp数组
1.确定dp数组以及下标的含义
dp[i][j]表示，从n个物品的前i个里面任意取，放进容量为j的背包，价值总和最大是dp[i][j]。
2.确定递推公式
对于第i个物品，有两种选择，不放到背包，或者放到背包。如果不放到背包，则dp[i][j]和dp[i-1][j]相等；如果放到背包，则dp[i][j]=dp[i-1][j-w[i]]+v[i]，这里需要限制j>=w[i]。因为要求最大值，所以应该是以上两种情况种较大的值，得到如下递推公式：
dp[i][j]=max(dp[i-1][j] , dp[i-1][j-w[i]]+v[i]);
3.dp数组初始化，当i为0时，表示不选物品，所以最大值都为0；当j为0时，表示背包容量为0，最大值也都为0；其他下标的值，都是根据表中左上方的到的，所以初始值都会被覆盖，不需要特殊处理。
4.确定遍历顺序，先遍历物品和先遍历背包都一样，选择先遍历物品。
5.举例推导dp数组