一、问题引入爬楼梯是动态规划的经典入门问题题目描述如下有10级台阶一次只能走1步或2步请问一共有多少种走法二、动态规划思路解析动态规划的核心是记录子问题答案避免重复计算我们可以通过递推的方式逐步求解初始状态第1级台阶只有1种走法直接走1步即dp[1] 1第2级台阶有2种走法走两次1步或直接走2步即dp[2] 2递推公式走到第n级台阶的走法等于走到第n-1级的走法再走1步加上走到第n-2级的走法再走2步即dp[n] dp[n-1] dp[n-2]计算过程按照递推公式逐步计算dp[3] dp[2] dp[1] 2 1 3dp[4] dp[3] dp[2] 3 2 5dp[5] dp[4] dp[3] 5 3 8dp[6] dp[5] dp[4] 8 5 13dp[7] dp[6] dp[5] 13 8 21dp[8] dp[7] dp[6] 21 13 34dp[9] dp[8] dp[7] 34 21 55dp[10] dp[9] dp[8] 55 34 89三、代码实现1. C语言实现#include stdio.h int main() { int dp[11]; dp[0] 1; // 边界条件第0级台阶有1种走法不走 dp[1] 1; for (int i 2; i 10; i) { dp[i] dp[i-1] dp[i-2]; } printf(10级台阶的走法总数%d\n, dp[10]); return 0; }2. Python实现def climb_stairs(n): if n 1: return 1 dp [0] * (n 1) dp[1] 1 dp[2] 2 for i in range(3, n 1): dp[i] dp[i-1] dp[i-2] return dp[n] print(10级台阶的走法总数, climb_stairs(10))3. 空间优化版C语言#include stdio.h int main() { int a 1, b 2; if (10 1) { printf(10级台阶的走法总数1\n); return 0; } for (int i 3; i 10; i) { int c a b; a b; b c; } printf(10级台阶的走法总数%d\n, b); return 0; }四、总结动态规划的核心是拆分问题记录子问题结果避免重复计算。爬楼梯问题的递推公式为dp[n] dp[n-1] dp[n-2]本质是斐波那契数列的应用。可以通过空间优化将空间复杂度从O(n)降低到O(1)。 点赞 收藏 关注获取更多算法入门内容
