# 动态规划之 -- 背包问题
背包问题是动态规划系列中经典的一类题型。它浓缩了动态规划最精髓的 状态 + 选择 的特点。通过解决背包问题，能够帮助我们最直观的思考一个动态规划问题究竟是如何推导出来的。
背包问题大概可分为两类：0-1 背包问题 与 完全背包问题。
# 0-1 背包问题
0-1 背包问题的题型为：有 M 个物品，每样物品都有各自的价值 a 与体积 b，使用一个容积为 N 的背包，如何选择物品，将背包装满，且此时价值最大。
这种题型的特点在于，每样物品只有取和不取两种选择，不能取多次，也不能取一半。因此解题的关键为物品的取舍。
因此，此种情况下建立的 dp 表的大小为 dp[M+1][N+1]。通过遍历每个物品 i，以及当前的背包容量 j，获取当前可以装下的最大价值 dp[i][j]。最终返回结果 dp[M][N]。
const M = obj.length
const dp = Array(M + 1)
.fill(0)
.map(x => Array(N + 1).fill(0));
初始化 base case
for (let i = 1; i < M; i++) {
for (let j = 0; j < N; j++) {
dp[i][j] = Math.max（选取 i 的结果， 不选取 i 的结果）
// ep:
// if (j < nums[i]) dp[i][j] = dp[i-1][j]
// else dp[i][j] = Math.max(dp[i-1][j - nums[i]] ,dp[i-1][j])
}
}
return dp[M][N];
遍历框架确定了，剩余的又回到了动态规划的关键问题，确立 base 数值，并获取状态转移方程。在本题型中即为：选取 i 的结果与不选取 i 的结果。找出规律后填空即可。
题型参考：
[416] 分割等和子集[474] 一和零[494] 目标和[879 盈利计划[1049] 最后一块石头的重量 II[1230] 抛掷硬币
# 完全背包问题
同样是有限的背包，有限种类的物品价值与重量，完全背包问题相比 0-1 背包问题，区别仅在于：每样物品的数量是无限的。
在解题思路与算法框架上仍然一致，围绕选择与状态来进行思考。
与 0-1 背包问题稍有不同的是，由于物品数量无限，通常选择该物品后的结果，往往是不需要基于上一个可选择物品做比对的。
例如：在 0-1 背包中选择状态所记录的值为 dp[i-1][j - nums[i]]，往往需要更改为 dp[i][j - nums[i]]。同时我们可以注意到，这样记录值通常与 dp[i] 是无关的，因此往往可以少建立一个维度的 dp 数组。
题型参考：
[322] 零钱兑换[518] 零钱兑换 II[1449] 数位成本和为目标值的最大数字[279] 完全平方数