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

一、先明确核心概念（新手易懂版）

• 状态：就是 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 {
     m = grid.(), n = grid[].();
    vector<vector<>> (m, <>(n));
    dp[][] = grid[][];
    
     ( j=; j<n; j++) dp[][j] = dp[][j] + grid[][j];
    
     ( i=; i<m; i++) dp[i][] = dp[i][] + grid[i][];
    
     ( i=; i<m; i++) {
         ( j=; j<n; j++) {
            dp[i][j] = (dp[i][j], dp[i][j]) + grid[i][j]; 
        }
    }
     dp[m][n];
}