算法思想-动态规划

爬楼梯

假设你正在爬楼梯。需要 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 阶

递归解决

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

递归的方式好理解，但是提交的时候会超时，为什么会超时，就像上图的二叉树似的，我们的f(4)被计算了两次f(3)被计算了三次，这还只是n=6的情况下，那我们怎么来减少重复的计算呢，那就是将已经计算过的放到hashmap里，有的话，直接返回，没有的话，就放到hashmap里

记忆化递归

class Solution {
    public int climbStairs(int n) {
        if (n==1){
            return 1;
        }
        if (n==2){
            return 2;
        }
        Map<Integer,Integer> map=new HashMap<>();
        if (null!=map.get(n)){
            return map.get(n);
        }else {
            int result= climbStairs(n-1)+climbStairs(n-2);
            map.put(n,result);
            return result;
        }
    }
}

就算是这样，也很慢，那我们就继续简化，我们发现递归是从上到下的，会造成很多次重复调用函数的开销，那么我们怎么去掉这些开销呢，反过来是不是就可以了？然后就像记忆化递归一样，将已经计算过的保存下来

动态规划

class Solution {
    public int climbStairs(int n) {
        if (n==1){
            return 1;
        }
        if (n==2){
            return 2;
        }
        int[] limit = new int[n+1];
        limit[1]=1;
        limit[2]=2;
        //新建一个数组，里面的limit[0]是空的，其余的从1开始的，也就是n，对应的爬楼梯的方法的和，就是3楼有3种方法，4楼有5种方法。
        //这就是为什么长度是n+1，因为第0个是空的
        for (int i=3;i<=n;i++){
            limit[i]=limit[i-1]+limit[i-2];
        }
        return limit[n];
    }
}