9-2 第一个动态规划问题 Climbing Stairs

70 climbling stairs

You are climbing a stair case. It takesnsteps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note:Givennwill be a positive integer.

Input: 2
Output:  2
Explanation:  There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

自顶向下的分析该问题：若我们要爬n阶台阶，我们每次或者爬1阶台阶或者2阶台阶，所以爬n阶台阶有两种可能

因为问题就变成了爬n-1阶台阶有多少种方法， 爬n-2阶台阶有多少种方法， 之后这两种答案的相加就好了

同样的，如果我想知道爬n-1阶台阶有多少种方法，我们只需要知道爬n-2阶台阶有多少种方法， 爬n-3阶台阶有多少种方法我们当然可以写出递归调用的代码

class Solution {
    public int climbStairs(int n) {
       if(n == 1) return 1;
       if(n == 2) return 2;
        return climbStairs(n-1) + climbStairs(n-2);   
    }
}

但leetcode会显示不ac原因是：Time Limit Exceeded

跟之前的菲波那切数列的分析一样，我们可以看到，

整个程序进行了非常多重叠的子结构

那么，我们可以考虑使用dp来优化

class Solution {
    public int climbStairs(int n) {
        if(n < 0)  return 0;
        if(n ==1)  return 1;
        int[] memo = new int[n];
        memo[0] = 1;
        memo[1] = 2;
        for(int i = 2; i<n; i++){
            memo[i] = memo[i-1] + memo[i-2];
        }
        return memo[n-1];
    }
}

练习：120

64