课程进度 83% · 第9/10章第9/10章 · 标签 1/3
— 1 —
动态规划基本原理
动态规划（DP）解决具有最优子结构和重叠子问题的问题，核心步骤：
- 定义状态：确定DP数组/表的含义（如dp[i]表示问题规模为i的解）
- 状态转移方程：找出状态之间的递推关系（如dp[i] = f(dp[i-1], dp[i-2], ...)）
- 初始化：设置边界条件（如dp[0], dp[1]的初值）
- 计算顺序：通常从小到大，确保计算当前状态时所依赖的状态已计算完毕
cpp
1
// 斐波那契数列的DP实现
2
int fibDP(int n) {
3
if (n <= 1) return n;
4
vector<int> dp(n + 1);
5
dp[0] = 0; dp[1] = 1; // 初始化
6
for (int i = 2; i <= n; ++i) {
7
dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移方程
8
}
9
return dp[n];
10
}
11
// 空间优化版本
12
int fibDP2(int n) {
13
if (n <= 1) return n;
14
int a = 0, b = 1;
15
for (int i = 2; i <= n; ++i) {
16
int c = a + b; a = b; b = c;
17
}
18
return b;
19
}
— 2 —
经典DP模型
线性DP — 最长递增子序列（LIS）
cpp
1
// 最长递增子序列 (LIS)
2
int lengthOfLIS(vector<int>& nums) {
3
int n = nums.size();
4
if (n == 0) return 0;
5
vector<int> dp(n, 1);
6
for (int i = 1; i < n; ++i)
7
for (int j = 0; j < i; ++j)
8
if (nums[i] > nums[j])
9
dp[i] = max(dp[i], dp[j] + 1);
10
return *max_element(dp.begin(), dp.end());
11
}
区间DP — 戳气球问题
cpp
1
// 戳气球问题
2
int maxCoins(vector<int>& nums) {
3
int n = nums.size();
4
nums.insert(nums.begin(), 1);
5
nums.push_back(1);
6
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
7
for (int len = 1; len <= n; ++len)
8
for (int i = 1; i <= n - len + 1; ++i) {
9
int j = i + len - 1;
10
for (int k = i; k <= j; ++k)
11
dp[i][j] = max(dp[i][j],
12
dp[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + dp[k+1][j]);
13
}
14
return dp[1][n];
15
}
DP状态定义转移方程初始化LIS