Leetcode-70. 爬楼梯

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

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

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

解法：1. 递推，时间复杂度O(N)，空间复杂度O（N），也可以减少到O（1），不用数组。2. 递归+存储

  • Java
    使用递推 
class Solution {
   
    public int climbStairs(int n) {
   
        if (n<=2) return n;
        int[] memory = new int[n];
        memory[0] = 1;
        memory[1] = 2;
        for (int i=2;i<n;i++) {
   
            memory[i] = memory[i-1] + memory[i-2];
        }
        return memory[n-1];
    }
}

使用递归+记忆化

class Solution {
   
    public int climbStairs(int n) {
   
        if (n<=2) return n;
        int res = this.helper(n, new int[n+1]);
        return res;
    }
    public int helper(int n, int[] memory) {
   
        if (n<=2) return n;
        if (memory[n]==0) {
   
            memory[n] = this.helper(n-1, memory) + this.helper(n-2, memory);
        }
        return memory[n];
    }
}
  • Python 
class Solution:
    def climbStairs(self, n: int) -> int:
        if n<=2: return n
        memory = [0]*n
        memory[0], memory[1] = 1, 2
        for i in range(2,n):
            memory[i] = memory[i-1] + memory[i-2]
        return memory[n-1]