背包小总结 (01背包、完全背包)

背包问题最重要的就是两点：递推公式和遍历顺序

背包问题面试常考的就是 01背包和完全背包。

其中 01背包中物品只能选一次，完全背包中物品可以无限次选取

背包类型主要有两种题型：

1. 求使背包装尽可能装满能获取的最大/最小价值或装满背包的最大/最小物品个数

递推公式

最大/最小价值：dp[j] = max or min(dp[j], dp[j - weight[i]] + value[i]);

最大/最小物品个数：dp[j] = Math.max or min(dp[j], dp[j - coins[i]] + 1);

初始化

最少：dp[0]=0; 其他的初始化为正无穷最多：全初始化为0就行（前提是coins中元素全为正数；否则，需要把负元素在dp中对应的位置初

始化为负无穷）

1. 求使背包装满的方案数（主要有两种情况组合数（顺序无关）和排列数（顺序有关））

递推公式：都是 dp[j] += dp[j - nums[i]];

但是二者内外层的遍历顺序不同：

组合数：外层for循环遍历物品，内层for遍历背包。

排列数：外层for遍历背包，内层for循环遍历物品。

背包的遍历顺序：

1. 01 背包

01 背包中二维 dp 数组的两个 for 遍历的内外循序是可以颠倒的

这里内外层都是从小到大遍历 01 背包中一维 dp 数组的两个 for 循环内外循序一定是先遍历物品，再遍历背包容量

注意：内层循环（背包容量）必须倒序遍历，保证每个物品只取一次。

1. 完全背包

在完全背包中，对于一维 dp 数组来说，其实两个 for 循环嵌套顺序同样无所谓（仅限于纯完全背包问题！）