爬楼梯

1. 题目描述

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

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

示例 1：*

输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶 示例 2：

输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

1 <= n <= 45

2. 分析

一共n阶楼梯，每次可以爬1阶或2个台阶。 现在设F(n)表示n阶楼梯的方法数量，那么F(2)表示只有2阶楼梯的上楼的方法。F(n-1)表示楼梯只有n-1阶时上楼方法。

假设最后一脚上了1个阶梯，那么上楼的方法是不是就由F(n-1)决定，也就是说此时F(n)=F(n-1)

假设最后一脚上了2个阶梯，那么上楼的方法是不是就由F(n-2)决定，也就是说此时F(n)=F(n-2)

这两种情况放在一起 F(n)=F(n-1)+F(n-2)

3. 代码

代码1：

def stairs(n: int) -> int:
    if n == 0 or n == 1:
        return 1
    return stairs(n - 1) + stairs(n - 2)
if __name__ == '__main__':
    n=20
    print(stairs(n))

代码2：

def stairs(n: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[-1]
if __name__ == '__main__':
    n=20
    print(stairs(n))

代码3：

def stairs(n: int) -> int:
    a = b = 1
    for i in range(2, n + 1):
        a, b = b, a + b
    return b
if __name__ == '__main__':
    n=20
    print(stairs(n))

Java代码：

class Solution {
    public int climbStairs(int n) {
         递归-O(2^n)
          if(n==1)
              return 1;
          if(n==2)
              return 2;
          return climbStairs(n-1)+climbStairs(n-2);

         动态规划-O(n)
          if(n==1)
              return 1;
          int dp[] = new int [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];

         斐波那契数列滚动数组O(n)
          if(n==1){
              return 1;
          }
          int first =1;
          int second=2;
          for(int i=3;i<=n;i++){
              int third = first+second;
              first =second;
              second =third;
          }
          return second;
         通项公式矩阵O(log(n))
          int[][] q = {{1, 1}, {1, 0}};
          int[][] res = pow(q, n);
          return res[0][0];
         通项公式O(log(n))
         public class Solution {
     public int climbStairs(int n) {
         double sqrt5 = Math.sqrt(5);
     double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
       return (int) Math.round(fibn / sqrt5);
     }
 }
         记忆化递归O(n)
          int meno[] =new int [n+1];
          return climbStairsMeno(n,meno);
    }
      public int [][]pow(int [][]a,int n){
          int[][]ret = {{1,0},{0,1}};
          while(n>0){
              if((n&1)==1){
                  ret=multiply(ret,a);
              }
              n>>=1;
              a=multiply(a,a);
          }
          return ret;
      }
       public int[][] multiply(int[][] a, int[][] b) {
          int[][] c = new int[2][2];
          for (int i = 0; i < 2; i++) {
              for (int j = 0; j < 2; j++) {
                  c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
              }
          }
          return c;
      }

      public int climbStairsMeno(int n,int meno[]){
          if(meno[n]>0)
              return meno[n];
          if(n==1)
              meno[n]=1;
          else if(n==2)
              meno[n]=2;
          else
              meno[n]=climbStairsMeno(n-1,meno)+climbStairsMeno(n-2,meno);
          return meno[n];
      }
}