-
动态规划问题的一般形式是求最值
-
求解动态规划问题的核心是穷举
-
存在**「重叠子问题」**
-
具备**「最优子结构」**
-
穷举的关键是**「状态转移方程」**
-
状态转移方程思维框架：
明确「状态」 -> 定义 DP 数组/函数的含义 -> 明确「选择」 -> 明确 base case
- 简单递归暴力求解
int fib(int N) {
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}递归问题的时间复杂度怎么算？子问题个数 * 子问题的时间复杂度
int fib(int N) {
vector<int> dp(N + 1, 0);
// base case
dp[1] = dp[2] = 1;
for (int i = 3; i <= N; i++)
dp[i] = dp[i - 1] + dp[i - 2];
return dp[N];
}动态转移方程：
- 进一步优化：仅保留之前的两个状态即可
int fib(int n) {
if (n == 2 || n == 1)
return 1;
int prev = 1, curr = 1;
for (int i = 3; i <= n; i++) {
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}要符合「最优子结构」，子问题间必须互相独立
int coinChange(vector<int>& coins, int amount) {
// 数组大小为 amount + 1，初始值也为 amount + 1
vector<int> dp(amount + 1, amount + 1);
// base case
dp[0] = 0;
for (int i = 0; i < dp.size(); i++) {
// 内层 for 在求所有子问题 + 1 的最小值
for (int coin : coins) {
// 子问题无解，跳过
if (i - coin < 0) continue;
dp[i] = min(dp[i], 1 + dp[i - coin]);
}
}
return (dp[amount] == amount + 1) ? -1 : dp[amount];
}- 先思考「如何穷举」，再追求「如何聪明地穷举」