爬楼梯 —— 从动态规划到斐波那契数列

引言在算法学习过程中有这样一道经典问题假设面前有一段楼梯每次可以向上爬1 个台阶2 个台阶那么到达第 n 阶楼梯一共有多少种不同的方法例如n 3可能的方案1 1 1 1 2 2 1共3 种这就是 LeetCode 70 —— 爬楼梯。虽然题目看起来简单但它实际上揭示了动态规划中最重要的思想将复杂问题拆分为若干规模更小的子问题。题目描述给定整数 n1 n 45每次可以爬1阶 或 2阶求到达第 n 阶的方法总数从小规模开始观察规律动态规划最重要的一步找规律。n 11只有一种方案[1]因此f(1)1n 2方案11 2共f(2)2n 3方案111 12 21共f(3)3n 4方案1111 112 121 211 22共f(4)5继续列举n方法数1122334558613有没有发现1 2 3 5 8 13 ...这正是斐波那契数列。状态转移方程推导这是整道题最核心的部分。思考最后一步假设我们要到达第 n 阶那么最后一步只有两种可能情况1最后跨1阶例如第 n-1 阶 ↓ 第 n 阶那么到达第 n 阶的方法数f(n-1)情况2最后跨2阶例如第 n-2 阶 ↓ 第 n 阶方法数f(n-2)总方法数根据加法原理到达第n阶的方法 最后跨1阶的方法 最后跨2阶的方法得到经典状态转移方程f(n)f(n-1)f(n-2)这正是斐波那契数列。动态规划解法状态定义设dp[i]表示到达第 i 阶楼梯的方法数初始状态根据题意dp[1] 1; dp[2] 2;状态转移根据刚刚推导dp[i] dp[i-1] dp[i-2];完整代码#include iostream #include vector using namespace std; class Solution { public: int climbStairs(int n) { if (n 2) { return n; } int prev2 1; int prev1 2; for (int i 3; i n; i) { int curr prev1 prev2; prev2 prev1; prev1 curr; } return prev1; } }; int main() { Solution solution; // Test case 1 int n1 2; int result1 solution.climbStairs(n1); cout Test case 1: endl; cout Input: n 2 endl; cout Output: result1 endl; cout Expected: 2 endl; cout endl; // Test case 2 int n2 3; int result2 solution.climbStairs(n2); cout Test case 2: endl; cout Input: n 3 endl; cout Output: result2 endl; cout Expected: 3 endl; return 0; }DP数组演示以n 6为例idp[i]1122334558613计算过程dp[3]123 dp[4]235 dp[5]358 dp[6]5813最终13空间优化观察转移方程dp[i] dp[i-1] dp[i-2];我们发现只依赖前两个状态因此整个数组其实没有必要保存。只需要两个变量即可。优化思路设a dp[i-2] b dp[i-1]那么c a b随后a b b c不断滚动更新。优化代码class Solution { public: int climbStairs(int n) { if(n 2) return n; int a 1; int b 2; for(int i 3; i n; i) { int c a b; a b; b c; } return b; } };复杂度分析动态规划时间复杂度 O(n) 空间复杂度 O(n)滚动数组优化时间复杂度 O(n) 空间复杂度 O(1)为什么它是动态规划入门第一题这道题几乎包含了动态规划最核心的思想最优子结构第 n 阶的答案依赖第 n-1 阶 第 n-2 阶重叠子问题计算f(6)时会反复计算f(5) f(4) f(3) ...状态转移能够建立递推关系f(n)f(n-1)f(n-2)从爬楼梯到斐波那契数列实际上f(1)1 f(2)2与标准斐波那契F(1)1 F(2)1略有区别。两者关系f(n)F(n1)例如nf(n)1122334558613因此LeetCode 70 本质上是一道“换皮版”的斐波那契数列问题。算法思想总结爬楼梯虽然是一道简单题却是动态规划领域最经典的入门案例。它向我们展示了动态规划的完整思维过程从小规模数据寻找规律定义状态dp[i]建立状态转移方程设置边界条件通过递推求解最终答案进一步进行空间优化最终得到f(n)f(n-1)f(n-2)这个看似简单的公式正是动态规划思想的起点也是后续学习背包问题、区间DP、树形DP以及状态压缩DP的重要基础。