分类
转移方程
- 问能否能装满背包(或者最多装多少):dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
- 问装满背包有几种方法:dp[j] += dp[j - nums[i]];
- 动态规划:494.目标和(opens new window)
- 动态规划:518. 零钱兑换 II(opens new window)
- 动态规划:377.组合总和Ⅳ(opens new window)
- 动态规划:70. 爬楼梯进阶版(完全背包)
- 问背包装满最大价值:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
- 问装满背包所有物品的最小个数:dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
0-1背包
- 二维数组 先遍历物品还是先遍历背包都可以,且第二层for循环是从小到大遍历;
一维数组 只能先遍历物品再遍历背包容量,且第二层for循环是从大到小遍历
完全背包
经典完全背包问题先遍历物品还是先遍历背包都可以,且第二层for循环是从小到大遍历。
排列组合问题:
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
- 求最小数,则两层for循环的先后顺序无所谓