爬楼梯

### C语言实现爬楼梯问题的解决方案 #### 方法一：递归方法 递归是一种直观的方式解决爬楼梯问题。以下是基于引用中的递归思想[^2]实现的一个简单例子： ```c int climbStairs(int n) { if (n == 1) { return 1; } else if (n == 2) { return 2; } else if (n > 2) { return climbStairs(n - 1) + climbStairs(n - 2); } } ``` 这种方法虽然易于理解，但在处理较大的输入时会非常低效，因为存在大量的重复计算。 --- #### 方法二：动态规划（数组存储） 为了优化递归方法的时间复杂度，可以采用动态规划的思想[^3]。通过使用一个数组来保存中间状态的结果，避免重复计算。 下面是具体的代码示例： ```c #include <stdio.h> int climbStairsDP(int n) { if (n <= 0) return 0; if (n == 1 || n == 2) return n; int dp[n + 1]; 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 main() { int steps = 5; printf("Number of ways to climb %d stairs: %d\n", steps, climbStairsDP(steps)); return 0; } ``` 上述代码中，`dp[i]` 表示到达第 `i` 阶楼梯的不同方式数量。最终返回的是 `dp[n]` 的值。 --- #### 方法三：空间优化的动态规划 如果只关心最后的结果而不需要整个数组的状态，则可以通过两个变量代替完整的数组，进一步减少内存消耗[^1]。 下面是一个更高效的版本： ```c #include <stdio.h> int climbStairsOptimized(int n) { if (n <= 0) return 0; if (n == 1 || n == 2) return n; int a = 1, b = 2, temp; for (int i = 3; i <= n; ++i) { temp = a + b; a = b; b = temp; } return b; } int main() { int steps = 5; printf("Number of ways to climb %d stairs: %d\n", steps, climbStairsOptimized(steps)); return 0; } ``` 此方法仅需常数级别的额外空间即可完成计算。 --- #### 总结 以上三种方法分别展示了如何利用 **递归** 和 **动态规划** 来解决问题。其中，递归方法适合初学者理解和学习逻辑结构，但实际应用中应优先考虑动态规划及其优化形式以提升性能和降低资源开销。 ---