动态规划
1.0 总体思想
目标：求最值；
核心：穷举、遍历；手段：列出正确的“状态转移方程”；
优化：去除“重叠子问题”；
三要素：重叠子问题、最优子结构、状态转移方程（难）；
关于状态转移方程：
base case是什么？
状态：问题的“状态”；
选择：做什么“选择”，可以改变“状态”
dp数组：如何定义dp数组来表现“状态”和“选择”
代码框架：
1
2
3
4
5
6
7
8
9# 初始化 base case
dp[0][0][...] = base case
# 遍历所有状态的可能取值
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for 状态3 in 状态3的所有取值:
...
# 状态转移方程
dp[状态1][状态2][状态3][...] = 最优值(选择1,选择2,...)1.1 斐波那契数列的解法：
暴力递归（自顶而下的思路）（递归函数）：
1
2
3
4
5int fib(int N) {
if (N == 0) return 0;
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}“备忘录”去除“重叠子问题”的递归（自顶而下）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
// 主函数，计算第 N 个斐波那契数
int fib(int N) {
if (N == 0) return 0;
// 创建一个大小为 N+1 的数组，用于记忆化
vector<int> memo(N + 1, 0);
return helper(memo, N);
}
// 递归辅助函数，带记忆化搜索
int helper(vector<int>& memo, int n) {
if (n == 1 || n == 2)
return 1; // 基础情况：fib(1) = fib(2) = 1
if (memo[n] != 0)
return memo[n]; // 如果已计算过，直接返回
// 否则递归计算并保存结果
memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
return memo[n];
}dp数组的迭代解法（自下而上）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
using namespace std;
int fib(int N) {
if (N == 0) return 0;
if (N == 1 || N == 2) return 1;
// 定义一个大小为 N+1 的数组用于动态规划
vector<int> dp(N + 1, 0);
dp[1] = dp[2] = 1; // 初始化前两个斐波那契数
// 自底向上填表
for (int i = 3; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}dp数组的空间优化（状态压缩）：
1
2
3
4
5
6
7
8
9
10
11
12int fib(int N) {
if (N == 0) return 0;
if (N == 1 || N == 2) return 1;
int prev = 1, curr = 1;
// 从第 3 项开始迭代计算
for (int i = 3; i <= N; i++) {
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}状态压缩用于将所需dp table的空间进行压缩
1.2 凑零钱问题
暴力递归（自顶而下）（dp函数迭代）：
思路：
初始状态：dp[0] = 0
dp[amount]是求解的值
对于coins数组中，每种硬币都有：dp[amout] = min(dp[amount], 1 + dp[amount-1])
伪代码
1
2
3
4
5
6def coinChange(coins:List[int], amount:int):
def dp(n):
for coin in coins:
dp(n) = min(res, 1 + dp(n-1))
return res
return dp(amount)代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17from typing import List
def coinChange(coins: List[int], amount: int) -> int:
# 定义递归函数 dp(n)：表示凑出金额 n 所需的最少硬币数
def dp(n):
if n == 0:
return 0 # 凑出 0 元需要 0 个硬币
if n < 0:
return -1 # 无法凑出负金额，返回 -1 表示无解
res = float('inf') # 初始化结果为正无穷（表示当前最小硬币数）
for coin in coins:
subproblem = dp(n - coin) # 子问题：凑出 n - coin 的最少硬币数
if subproblem == -1:
continue # 子问题无解，跳过
res = min(res, 1 + subproblem) # 当前结果为子问题结果 + 1 枚硬币
return res if res != float('inf') else -1 # 如果 res 没有被更新，说明无解
return dp(amount) # 返回凑出 amount 所需的最少硬币数备忘录，在dp数组外建立一个备忘录memo，在dp(n)里面判断，是否计算过，有的话，直接返回memo[n]即可，没有的话，要在dp[n]计算完毕后，加入备忘录
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19def coinChange(coins: list[int], amount: int) -> int:
memo = dict() # 用于记忆化缓存中间结果
def dp(n: int) -> int:
if n in memo:
return memo[n]
if n == 0:
return 0 # 凑出金额 0，硬币数为 0
if n < 0:
return -1 # 负数金额无法凑出，视为无解
res = float('inf')
for coin in coins:
subproblem = dp(n - coin)
if subproblem == -1:
continue # 子问题无解，跳过
res = min(res, 1 + subproblem) # 选择当前最优方案
# 记录子问题的计算结果，避免重复计算
memo[n] = res if res != float('inf') else -1
return memo[n]
return dp(amount)dp数组的迭代解法（自下而上）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14int coinChange(vector<int> coins, int amount) {
// dp[i] 表示：凑出金额 i 所需的最少硬币数
vector<int> dp(amount + 1, amount + 1); // 初始化为最大值 amount+1（相当于正无穷）
dp[0] = 0; // 凑出金额 0，需要 0 个硬币
for (int i = 1; i <= amount; i++) { // 枚举金额 i
for (int coin : coins) { // 枚举每个硬币
if (i - coin < 0) continue; // 当前硬币不能使用（太大了）
dp[i] = min(dp[i], dp[i - coin] + 1); // 状态转移：用掉一个 coin
}
}
return (dp[amount] == amount + 1) ? -1 : dp[amount]; // 没被更新就说明无解
}
