f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下状态方程：

f(x)=f(x−1)+f(x−2)

记忆化搜索：

设置int[]dp数组，int[n]表示f(x)，n=1,2时直接返回。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int climbStairs(int n) {
       if(n==1)return 1;
       if(n==2)return 2;
       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];
    }
}