重练算法（代码随想录版） day37 - 动态规划part5

补12.11日任务
今日刷题量：4
当前刷题总量：143
Easy: 59
Mid: 77
Hard: 7

Day37
常用思想
完全背包（每种物品可选无限次）解题时先抓住 3 件事：状态怎么定义、转移怎么写、循环顺序怎么安排。

判题型：求最大值还是求方案数

• 最值类：最大价值/最少物品数/是否可达
• 计数类：方案数（组合 or 排列）

这决定 dp 的含义和初始化。

• 完全背包最值：物品外层，容量递增
• 完全背包组合计数：物品外层，容量/目标递增
• 完全背包排列计数：目标外层，物品内层

练习题目
完全背包（mid）： https://kamacoder.com/problempage.php?pid=1052
518. 零钱兑换 II（mid）：https://leetcode.cn/problems/coin-change-ii/description/
377. 组合总和 Ⅳ （mid）：https://leetcode.cn/problems/combination-sum-iv/description/
70. 爬楼梯 （进阶）（mid）：https://kamacoder.com/problempage.php?pid=1067