一、先明确核心概念（新手易懂版）
- 状态：就是 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)）。
二、时间复杂度计算（核心公式）
公式：
时间复杂度 = 状态数量 × 单个状态的计算成本
分场景拆解（结合 C++ 例子）
场景 1：一维 DP（如斐波那契数列）
// 一维 DP：dp[i] = dp[i-1] + dp[i-2]
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]; // 单个状态计算成本：O(1)
}
return dp[n];
}
- 状态数量：需要计算
dp[3]到dp[n]，共n-2个状态，约等于 O(n)。 - 单个状态计算成本：算
dp[i]只需要做一次加法，是 O(1)。 - 时间复杂度：O(n) × O(1) = O(n)。
场景 2：二维 DP（如最小路径和）
// 二维 DP：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
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个状态，即 O(m*n)。 - 单个状态计算成本：算
dp[i][j]只需要一次 min 和一次加法，是 O(1)。 - 时间复杂度：O(m*n) × O(1) = O(mn)。
场景 3：单个状态计算成本非 O(1)（如完全背包）
// 完全背包：dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
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];
}
- 状态数量：背包容量是
bagSize，状态数是 O(bagSize)。 - 单个状态计算成本：每个状态需要遍历所有物品（数量为 n），是 O(n)。
- 时间复杂度：O(bagSize) × O(n) = O(n×bagSize)。
三、空间复杂度计算（核心：看存储的状态数）
核心逻辑：
空间复杂度 = 存储 DP 状态所用的额外空间（不包含输入空间），分'原始版'和'优化版'两种情况。
分场景拆解
场景 1：一维 DP 原始版（斐波那契）
vector<int> dp(n+1); // 存储 n+1 个状态
- 空间复杂度：O(n)（存储了 n+1 个 int，约等于 O(n)）。
场景 2：一维 DP 空间优化版（斐波那契）
// 只用两个变量存前两个状态，不用数组
int prev_prev = 1, prev = 1, curr;
- 存储的状态数：固定 2 个变量，和 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(min(m,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(1)，复杂度就是状态数。
- 空间复杂度：原始版等于存储的状态数（一维 O(n)、二维 O(mn)），优化版通过'复用空间'降维（比如二维→一维、一维→常数）。
- 优化空间不会改变时间复杂度，因为还是要计算所有状态，只是少存了中间结果。
