70.爬楼梯

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

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

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

示例 1：

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

Solution

很经典的动态规划题目，每爬一阶楼梯的方法取决于前一节和前两节的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    private int cnt =0;
    public int climbStairs(int n) {

        int f0,f1;
        f0=f1=1;
        for (int i = 1; i <n; i++) {
            int new_f=f0+f1;
            f0=f1;
            f1=new_f;  
        }
        return f1;
    }
}
// 可以看出公式是:dfs(n)=dfs(n-2)+dfs(n-1)
   /* public void dfs(int n){
        if(n<0){
            return ;
        }
        if(n==0){
           cnt++;
           return ;
        }
        dfs(n-2);
        dfs(n-1);
    }
   */