「算法模版」动态规划
「状态」-> 「选择」 -> 定义 dp 数组/函数的含义 ；自底向上进行递推求解。
# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
for 选择 in 所有可能的选择:
# 此时的状态已经因为做了选择而改变
result = 求最值(result, dp(状态1, 状态2, ...))
return result
# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...)
核心框架
备忘录 - 斐波那契数
int fib(int n) { if (n == 0 || n == 1) return n; // 分别代表 dp[i - 1] 和 dp[i - 2] int dp_i_1 = 1, dp_i_2 = 0; for (int i = 2; i <= n; i++) { int dp_i = dp_i_1 + dp_i_2; dp_i_2 = dp_i_1; dp_i_1 = dp_i; } return dp_i; }最优子结构 - 零点兑换
如何列出正确的状态转移方程？
- 确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额
amount。 - 确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。
- 明确
dp函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的dp函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。
定义
dp函数：dp(n)表示，输入一个目标金额n，返回凑出目标金额n所需的最少硬币数量。- 确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额
class Solution { public: vector<int> memo; int coinChange(vector<int>& coins, int amount) { memo = vector<int> (amount + 1, -666); // memo[amount] 表示凑成金额 amount 所需的最少硬币数 return dp(coins, amount); } int dp(vector<int>& coins, int amount) { if (amount == 0) return 0; if (amount < 0) return -1; if (memo[amount] != -666) return memo[amount]; // 已经计算过该金额，直接返回结果 int res = INT_MAX; // INT_MAX 表示当前金额的最小硬币数还未计算 for (int coin : coins) { // 找到子问题最优解 int subProblem = dp(coins, amount - coin); // 子问题：用当前硬币后，剩余金额所需的最少硬币数 if (subProblem == -1) continue; // 子问题无解则跳过 res = min(res, subProblem + 1); // 比较当前解和之前的最优解，确保 res 保存最小的硬币数 } memo[amount] = (res == INT_MAX) ? -1 : res; // 将计算结果存入备忘录 return memo[amount]; } };