代码随想录算法训练营day37|动态规划part5
今天的几道题目都比较简单，思路也比较相似，都是利用完全背包。完全背包和01背包的不同点在于完全背包每个元素可以取多次，而01背包只能取1次，所以在dp一维数组遍历时，完全背包仍然要从前往后遍历，并且无论是先遍历物品还是先遍历背包都可以，但是先遍历物品和先遍历背包在次数上是有差别的，只是在求最大价值时得到的结果相同。先遍历物品时，一定是前面的物品遍历完之后再遍历后面的物品，所以这是组合；在先遍历背包时，是用一个背包容量将所有物品扫过一遍后才查找下一个背包容量，所以满足要求的填满背包的物品有不同的顺序，所以这是排列
完全背包
视频讲解：
https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html
518. 零钱兑换 II
视频讲解：
https://programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html
377. 组合总和 Ⅳ
视频讲解：代码随想录
70. 爬楼梯 （进阶）
这道题目 爬楼梯之前我们做过，这次再用完全背包的思路来分析一遍
https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E7%89%88%E6%9C%AC.html