您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

算法思想-动态规划

算法思想-动态规划

爬楼梯

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

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进