每次爬 1 和 2 n=0 1 n=1 1 n=2 1+1 2 n=3 1+1+1 1+2 2+1 n=4 1+1+1+1 1+1+2 2+1+1 1+2+1 2+2 n=5 1+1+1+1+1 1+2+2 2+1+2 2+2+1 1+1+1+2 2+1+1+1 1+2+1+1 1+1+2+1 f(2) = f(1)+f(0) f(3) = f(2) + f(1) f(4) = f(3) + f(2) f(n) = f(n-1)+f(n-2) 根据推到的公式 编写代码如下：

    1. class Solution {
    2.     public int climbStairs(int n) {
    3.         //0. 通过递归的方式实现，不推荐 会爆栈
    4.         //if(n==1) return 1;
    5.         //if(n==2) return 2;
    6.         //return climbStairs(n-1) + climbStairs(n-2);
    8.         //1. 通过数组的方式保存，但是会占用大量的空间
    9.         // int result[] = new int[n+1];//只需要三个空间的数组
    10.         // result[0] = 1;
    11.         // result[1] = 1;
    12.         // for (int i = 2; i <=n; i++) {
    13.         //     result[i] = result[i-1] + result[i-2]; 
    14.         // }
    15.         //f(5) = f(4)->f(3)->f(2)+f(1)+f(2) = 5 + f(3)->f(2)+f(1) = 3
    16.         // return result[n];
    18.         //3.可以通过滚动DP的方式实现，优化占用的空间
    19.         if (n<=2) {
    20.             return n;
    21.         }
    22.         int q = 1;
    23.         int p = 2;
    24.         int r = 0;
    25.         for (int i = 3; i <=n; i++) {
    26.             r = q + p;//3
    27.             q = p;//2
    28.             p = r;//3
    29.         }
    30.         return r;
    31.     }
    32. }