动态规划时间复杂度等于状态数量乘以单个状态计算成本，常见为 O(1)。空间复杂度取决于存储的状态数，可通过滚动数组优化。文章通过斐波那契数列、最小路径和及背包问题等 C++ 示例，详细拆解了一维与二维 DP 的复杂度推导过程，并总结了典型问题的复杂度对比表，帮助开发者快速掌握动态规划性能分析方法。
dp[i]、dp[i][j] 这类表示子问题的变量，比如 dp[i] 是第 i 个斐波那契数，dp[i][j] 是前 i 个物品装容量 j 背包的最大价值。dp[i]）需要的操作数（通常是 O(1)，少数是 O(k)）。时间复杂度 = 状态数量 × 单个状态的计算成本
// 一维 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)。// 二维 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)。// 完全背包：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)。空间复杂度 = 存储 DP 状态所用的额外空间（不包含输入空间），分'原始版'和'优化版'两种情况。
vector<int> dp(n+1); // 存储 n+1 个状态
// 只用两个变量存前两个状态，不用数组
int prev_prev = 1, prev = 1, curr;
vector<vector<int>> dp(m, vector<int>(n)); // 存储 m×n 个状态
// 只用一维数组，覆盖更新
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))）。grid[m][n] 不算，只算自己定义的 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)） |
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online