动态规划时间复杂度与空间复杂度计算方法

二维数组 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)。

四、新手避坑点

1. 混淆'状态数量'和'循环次数'：循环次数本质就是状态数量。比如二维 DP 的两层循环，次数就是 m×n，对应状态数 m×n。
2. 忽略空间优化的影响：原始 DP 的空间复杂度等于状态数，但优化后可能降维（二维→一维→常数），时间复杂度通常不变（因为还是要算所有状态）。
3. 把输入空间算进去：复杂度只算'额外空间'。比如输入的 grid[m][n] 不算，只算自己定义的 dp 数组。

五、典型 DP 问题复杂度总结

总结

1. 时间复杂度：核心是「状态数量 × 单个状态计算成本」。大部分场景单个状态成本是 O(1)，复杂度就是状态数。
2. 空间复杂度：原始版等于存储的状态数（一维 O(n)、二维 O(mn)），优化版通过'复用空间'降维（比如二维→一维、一维→常数）。
3. 优化空间不会改变时间复杂度，因为还是要计算所有状态，只是少存了中间结果。