一、先明确核心概念
理解 DP 复杂度前，得先搞清楚三个基础要素：
- 状态：DP 里定义的
dp[i]、dp[i][j]这类表示子问题的变量。比如dp[i]是第 i 个斐波那契数，dp[i][j]是前 i 个物品装容量 j 背包的最大价值。 - 状态数量：所有需要计算的子问题总数。一维 DP 通常是 n，二维 DP 则是 n*m。
- 单个状态计算成本：算一个状态（比如
dp[i]）需要的操作数。通常是 O(1)，少数情况会涉及循环导致 O(k)。
二、时间复杂度计算
核心公式很简单：时间复杂度 = 状态数量 × 单个状态的计算成本。
场景 1：一维 DP（如斐波那契数列）
int fib_dp(int n) {
if (n <= 2) return 1;
vector<int> dp(n+1);
dp[1] = 1;
dp[2] = 1;
for (int i=3; i<=n; i++) {
dp[i] = dp[i-1] + dp[i-2]; // 单次计算仅需一次加法
}
return dp[n];
}
这里状态是从 dp[3] 到 dp[n]，约等于 O(n)。每个状态只需做一次加法，成本是 O(1)。所以总时间复杂度是 O(n)。
场景 2：二维 DP（如最小路径和）
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n));
dp[0][0] = grid[0][0];
// 初始化第一行
for (int j=1; j<n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
// 初始化第一列
for (int i=1; i<m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
// 计算其他状态
for (int i=1; i<m; i++) {
for (int j=1; j<n; j++) {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; // O(1)
}
}
return dp[m-1][n-1];
}
二维数组 dp[m][n] 意味着有 m×n 个状态。每个状态计算只需要一次 min 和一次加法，成本 O(1)。因此时间复杂度是 O(mn)。
场景 3：单个状态计算成本非 O(1)（如完全背包）
int completeKnapsack(vector<int>& weight, vector<int>& value, int bagSize) {
vector<int> dp(bagSize+1, 0);
for (int i=0; i<weight.size(); i++) { // 遍历物品
for (int j=weight[i]; j<=bagSize; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
}
}
return dp[bagSize];
}
注意这里的嵌套循环。虽然外层遍历物品，内层遍历容量，但逻辑上我们是在更新同一个一维数组的状态。如果按经典定义看，状态数是 O(bagSize)，但为了更新这些状态，我们需要遍历所有物品（数量为 n）。所以单个状态的'有效'计算成本包含了物品的遍历，整体时间复杂度为 O(n×bagSize)。
三、空间复杂度计算
空间复杂度主要看存储 DP 状态所用的额外空间（不包含输入数据），分原始版和优化版两种情况。
场景 1：一维 DP 原始版
vector<int> dp(n+1); // 存储 n+1 个状态
直接开数组，空间复杂度是 O(n)。
场景 2：一维 DP 空间优化版
// 只用两个变量存前两个状态，不用数组
int prev_prev = 1, prev = 1, curr;
只用了固定数量的变量，和 n 无关。空间复杂度降为 O(1)。
场景 3：二维 DP 原始版
vector<vector<int>> dp(m, vector<int>(n)); // 存储 m×n 个状态
空间复杂度是 O(mn)。
场景 4：二维 DP 空间优化版
// 只用一维数组，覆盖更新
vector<int> dp(n, 0);
dp[0] = grid[0][0];
for (int j=1; j<n; j++) dp[j] = dp[j-1] + grid[0][j];
for (int i=1; i<m; i++) {
dp[0] += grid[i][0]; // 第一列更新
for (int j=1; j<n; j++) {
dp[j] = min(dp[j], dp[j-1]) + grid[i][j]; // 覆盖旧值
}
}
这里只用了一维数组 dp[n]，状态数缩减为 O(n)。空间复杂度变为 O(n)。
四、新手避坑点
- 混淆'状态数量'和'循环次数'：循环次数本质就是状态数量。比如二维 DP 的两层循环，次数就是 m×n，对应状态数 m×n。
- 忽略空间优化的影响：原始 DP 的空间复杂度等于状态数，但优化后可能降维（二维→一维→常数），时间复杂度通常不变（因为还是要算所有状态）。
- 把输入空间算进去：复杂度只算'额外空间'。比如输入的
grid[m][n]不算，只算自己定义的dp数组。
五、典型 DP 问题复杂度总结
| 问题 | 状态定义 | 时间复杂度 | 原始空间复杂度 | 优化后空间复杂度 |
|---|---|---|---|---|
| 斐波那契数列 | dp[i] | O(n) | O(n) | O(1) |
| 最小路径和 | dp[i][j] | O(mn) | O(mn) | O(n) |
| 01 背包 | dp[i][j] | O(n×bagSize) | O(n×bagSize) | O(bagSize) |
| 最长递增子序列 | dp[i] | O(n²) | O(n) | O(n) |
总结
- 时间复杂度：核心是「状态数量 × 单个状态计算成本」。大部分场景单个状态成本是 O(1)，复杂度就是状态数。
- 空间复杂度：原始版等于存储的状态数（一维 O(n)、二维 O(mn)），优化版通过'复用空间'降维（比如二维→一维、一维→常数）。
- 优化空间不会改变时间复杂度，因为还是要计算所有状态，只是少存了中间结果。