首页 > 其他分享 > 最小花费爬楼梯 -- 动态规划

最小花费爬楼梯 -- 动态规划

时间:2022-10-29 15:15:31浏览次数:52  
标签:爬楼梯 递归 迭代 -- 花费 int cost 整型 public

方法一 递归 

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] cost) {
        return recursion(cost.length,cost);       
    }
    
    private int recursion(int i,int[] cost) {
        //登上0级或1级的成本为0
        if(i<2)
           return 0;
        //爬到第i级台阶的总花费
        return Math.min(recursion(i-1,cost) + cost[i-1],recursion(i-2,cost)+cost[i-2]);

    }
}

  运行超时 

5/10 组用例通过 运行时间2001ms 占用内存9816KB

 

方法二 :  循环

   

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] cost) {
        int[] dp = new int[cost.length+1];
        for(int i = 2 ; i<= cost.length ; i++){
              dp[i] = Math.min(dp[i-1]+cost[i-1] , dp[i-2]+cost[i-2]);
        }
        return dp[cost.length];
    }
}

  

通过全部用例 运行时间207ms 占用内存22528KB     结论: 从性能上来 看循环的方式迭代 大大优于 递归的方式迭代 ; 空间占用方面,循环方式稍高 2者的区别在于: a.  循环方式需要一个数组存放每轮迭代的结果,递归方式不需要 b.  循环方式从前向后迭代,每一步都把结果放进中间数组 , 递归方式为从后向前迭代

标签:爬楼梯,递归,迭代,--,花费,int,cost,整型,public
From: https://www.cnblogs.com/yanher/p/16838743.html

相关文章

  • python 的多行输入
    a,b=input().split("")#输入字符串(默认返回类型)a和b以(空格)分隔a,b,c=eval(input())#输入三个值(任何类型)中间由逗号分隔a,b,c=int(input())......
  • 第二次博客总结
     前言经历过一段时间的java学习并完成了三次大作业之后,在此分享我的一些感悟和心得。1.pta第四次作业为四边形的一些算法设计,在第第三次作业三角形上的进阶,难度较高,其......
  • java pta第二次阶段性总结
    一、前言     经过这三次的pta训练,我对java再一次有了一个新的认识,这三次比起之前难度更大,所涉及的知识点更多。第4、5次作业是在前几次作业上的再次拓展,由三角形拓......
  • 解决element-ui的textarea组件的宽度无法修改的问题
    1参考来自http://www.iis7.com/a/nr/wz/202108/53923.html2示例需要先找到改组件的样式然后进行修改http://www.iis7.com/a/nr/wz/202108/53923.html .textarea>>......
  • 实验7:基于REST API的SDN北向应用实践
    实验7:基于RESTAPI的SDN北向应用实践一、实验目的1.能够编写程序调用OpenDaylightRESTAPI实现特定网络功能;2.能够编写程序调用RyuRESTAPI实现特定网络功能。二、实......
  • HTML4学习随笔
    HTMLhtml:超文本标记语言(HyperTextMarkupLanguage)(html结构)(css表现)(js行为)<!DOCTYPEhtml><!--声明文档类型让浏览器以html的格式解析--><htmllang="en"><head......
  • 基于python指定包的安装路径方法(linux)
    通常python安装包都会被默认装在/usr/local/pythonx/lib/site-packages(linux),但是我们有时想自定义包的安装路径,比如自己项目的某个路径,这样在部署的时候就不用再安装了,大......
  • 虚拟机或者云服务器上使用code-server
    Ubuntu服务器安装code-server到gitrelease页面下载打包好的deb安装包下载地址:https://github.com/coder/code-server/releases>dpkg-icode-server_4.8.1_amd64.de......
  • 浏览器编辑pdf技术预研
    目录查阅文档1.jspdf2.pdftron3.pdf-lib查阅文档1.jspdfgit库:https://github.com/parallax/jsPDFapi文档:http://raw.githack.com/MrRio/jsPDF/master/docs/index.......
  • CMD中使用cd无法改变到D盘驱动器
    使用cdd:,想改到D盘驱动器,但无法实现使用cd/?查看cd命令的帮助原来在使用/D参数开关,才能改变驱动器,否则只能是当前驱动器 ......