背包类

• 用值作为 DP 维度
• DP 的过程就是填写矩阵
• 可以滚动数组优化

题目

Backpack

变形题:

1. 硬币凑整, 给1,2,5,10 硬币, 凑成80元的方案总数
2. 把一个数组[1,2,4,5,6]尽量平分

322. Coin Change

dp[i] = min(dp[i-coin] + 1, dp[i]), for i > coin

279. Perfect Squares

Backpack II

k Sum

Minimum Adjustment Cost

更详细的: 背包九讲