// 解法1，递归解法，时间复杂度为O(2^n)，会超时
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
// 解法2，递归解法，开辟一个长度为n的数组作为备忘录存放已经计算的结果，时间复杂度O(n),空间复杂度O(n)
public int climbStairs(int n) {
return climbStairs(n, new int[n + 1]);
}
public int climbStairs(int n, int[] mem) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
if (mem[n] != 0) {
return mem[n];
}
mem[n] = climbStairs(n - 1, mem) + climbStairs(n - 2, mem);
return mem[n];
}
// 解法3，动态规划，dp(n) = dp(n-1)+dp(n-2)
// 初始条件，dp(1) = 1，dp(2) = 2
// 数组压缩
public int climbStairs(int n) {
if (n == 1 || n == 2) {
return n;
}
int a=1,b=2,c=0;
for (int i = 3; i <=n; i ++) {
c = a + b;
a = b;
b = c;
}
return c;
}
