DP总结

其实就两点：状态（dp数组）和选择（min，max求最值）

0/1背包

定义：物品只能用一次

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

例：416. 分割等和子集、494.目标和

完全背包 定义：物品可以使用无限次 dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]] + value[i]) 区别与01背包就在于dp后一项的状态1仍为i

例：518. 零钱兑换 II

状态机

四维状态dp：乌龟跑步