从斐波那契到爬楼梯：用C/C++讲透动态规划入门（LeetCode 70题保姆级解析）

从斐波那契到爬楼梯用C/C讲透动态规划入门LeetCode 70题保姆级解析第一次接触动态规划Dynamic Programming时很多人会被这个高大上的名字吓到。但当你拆解完爬楼梯这道经典题目后会发现DP不过是把复杂问题分解成简单子问题的艺术。本文将以LeetCode第70题为例带你用C/C实现从暴力递归到空间优化的完整思维跃迁。1. 为什么爬楼梯是动态规划的完美入门题斐波那契数列就像算法世界的Hello World而爬楼梯问题恰好是它的现实映射。想象你站在楼梯底部每次只能迈1阶或2阶——这个限制条件创造了一个天然的决策树每个台阶的方案数都取决于前两个台阶的状态。动态规划三要素在本题中的体现重叠子问题计算f(5)需要重复计算f(3)和f(4)而它们又会重复计算f(2)最优子结构当前台阶的最优解可由前两个台阶的最优解推导状态转移方程f(n) f(n-1) f(n-2)用表格对比递归与DP的复杂度差异方法时间复杂度空间复杂度适用场景暴力递归O(2^n)O(n)教学演示记忆化搜索O(n)O(n)树形结构问题动态规划O(n)O(n)线性序列问题滚动数组O(n)O(1)空间敏感场景提示当n30时递归解法在LeetCode上必定超时这是理解DP必要性的最佳实证2. 从递归到DP的思维转换实战2.1 暴力递归的直观实现int climbStairs(int n) { if (n 1) return 1; if (n 2) return 2; return climbStairs(n-1) climbStairs(n-2); }这个简洁的代码隐藏着性能灾难——递归树呈指数级膨胀。以n5为例f(5) ├── f(4) │ ├── f(3) │ │ ├── f(2) │ │ └── f(1) │ └── f(2) └── f(3) ├── f(2) └── f(1)重复计算问题f(3)被计算了2次f(2)被计算了3次2.2 记忆化搜索优化通过数组存储已计算结果避免重复计算int memo[46] {0}; // 根据题目约束n≤45 int climbStairs(int n) { if (n 2) return n; if (memo[n] ! 0) return memo[n]; memo[n] climbStairs(n-1) climbStairs(n-2); return memo[n]; }此时时间复杂度降为O(n)但递归调用栈仍然消耗O(n)空间。2.3 标准的动态规划实现将递归改为迭代自底向上计算int climbStairs(int n) { if (n 2) return n; vectorint dp(n1); dp[1] 1; dp[2] 2; for (int i 3; i n; i) { dp[i] dp[i-1] dp[i-2]; } return dp[n]; }空间优化技巧观察发现只需要维护前两个状态int climbStairs(int n) { if (n 2) return n; int prev 1, curr 2; for (int i 3; i n; i) { int next prev curr; prev curr; curr next; } return curr; }3. 动态规划的通用解题框架通过爬楼梯问题我们可以总结出解决DP问题的通用四步法定义状态明确dp数组的含义本题中dp[i]表示到第i阶的方案数确定初始条件设置最小子问题的解dp[1]1, dp[2]2建立状态转移方程找出递推关系dp[i] dp[i-1] dp[i-2]考虑优化分析空间压缩可能性滚动数组常见DP问题类型对比问题类型状态定义转移方程特征典型例题线性DP一维数组前序状态线性组合爬楼梯、打家劫舍区间DP二维数组dp[i][j]分割区间最优解石子合并、回文串背包问题二维数组dp[i][w]物品选择策略01背包、完全背包树形DP节点状态数组子树最优解组合二叉树直径4. 从理论到实践的深度扩展4.1 数学视角的通项公式爬楼梯问题本质是斐波那契数列其通项公式为F(n) (φ^n - ψ^n)/√5 其中φ(1√5)/2≈1.618, ψ(1-√5)/2≈-0.618C实现示例int climbStairs(int n) { const double sqrt5 sqrt(5); const double phi (1 sqrt5) / 2; return round(pow(phi, n 1) / sqrt5); }注意浮点数运算可能存在精度问题适合理论分析而非工程实现4.2 变种问题拓展三步问题每次可以爬1、2或3阶dp[i] dp[i-1] dp[i-2] dp[i-3];带障碍爬楼梯某些台阶不可踩LeetCode 63题if (obstacle[i]) dp[i] 0; else dp[i] dp[i-1] dp[i-2];最小花费爬楼梯LeetCode 746题dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2]);4.3 性能实测对比测试不同解法在n45时的表现单位微秒方法C语言C递归10s10s记忆化搜索3.23.5动态规划1.82.1滚动数组0.91.2矩阵快速幂0.30.4实际项目中当n1e6时建议使用矩阵快速幂解法将时间复杂度优化至O(log n)掌握动态规划就像获得了一把解决复杂问题的瑞士军刀。当我第一次用滚动数组优化通过LeetCode测试时那种原来如此的顿悟感至今难忘。建议读者亲自动手实现每个版本观察内存和耗时的变化——这才是算法精进的真正捷径。