爬楼梯动态规划法

假设你正在爬楼梯。需要n阶你才能到达楼顶。

每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？

1. 问题分析：

   • 每次可以爬 1 或 2 个台阶
   • 要爬到 n 阶台阶，有多少种不同的方法

2. 思路推导：

   • 爬到第 n 阶台阶，最后一步只能是从 n-1 阶爬 1 阶，或者从 n-2 阶爬 2 阶
   • 所以递推关系是：f (n) = f (n-1) + f (n-2)
   • 边界条件：f (1) = 1（只有 1 种方法），f (2) = 2（两种方法）

class Solution {
public:
int climbStairs(int n) {
// 处理边界情况
if(n <= 2) return n;

// 动态规划解法，使用变量存储前两个状态，节省空间
int prev_prev = 1; // f(n-2)
int prev = 2; // f(n-1)
int current; // f(n)
for(int i = 3; i <= n; i++){
current = prev + prev_prev;
prev_prev = prev;
prev = current;
}

return prev;
}
};

1. 添加了#include <iostream>和using namespace std;以支持输入输出操作
2. 编写了main函数，实现用户交互
3. 添加了输入合法性检查，确保输入在题目要求的 1-45 范围内
4. 实例化了Solution类并调用climbStairs方法进行计算
5. 输出了清晰的结果提示

这种解法的时间复杂度是 O (n)，空间复杂度是 O (1)，因为我们只使用了有限的几个变量来存储中间结果，而没有使用数组。