动态规划之背包DP

2024-1-24
首先是 完全背包 和 0-1 背包：

同样是限制空间容量最大为 m，然后有 n 类物品，两者的区别在于：

① 完全背包中每一类物品有 ki 个，而 0-1 背包中每类物品只有 1 个。

② 实现上完全背包是正序循环的，而 0-1 背包是逆序循环的，因为前者需要考虑装多个物品的情况（这个从转移方程可以看出）

主要的应用场景：

① 经典的问题，直接敲板子上去交，注意，dp 一定要滚成一维，还有空间要开到 m 的最大取值。

② 遇到了凑数字这种题，给你一个凑数规则，问你怎么凑用到的数字数量最小，最小为几。

（未完待续。。。）