# 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：[乌龟跑步](niu-ke-wang/wu-gui-pao-bu)
