首页 > 其他分享 >力扣746 使用最小花费爬楼梯

力扣746 使用最小花费爬楼梯

时间:2023-02-22 22:35:44浏览次数:39  
标签:下标 上爬 台阶 746 int 力扣 cost 爬楼梯 dp

题目:

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

示例:

输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。
- 支付 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 。
输入:cost = [1,100,1,1,1,100,1,1,100,1]
输出:6
解释:你将从下标为 0 的台阶开始。
- 支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。
- 支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。
- 支付 1 ,向上爬一个台阶,到达楼梯顶部。
总花费为 6 。

思路:

先解析一下题目:用示例1说明,顶部台阶就是cost[3],支付15即可从cost[1](第一阶)选择爬2阶楼梯到cost[3](顶部台阶)。

最重要的两点:(1)你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。(2)可选择向上爬一个或者两个台阶。

其实这里就说明了,可以有两个途径得到dp[i],一个是dp[i-1] 一个是dp[i-2](一个台阶前或两个台阶前)。

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢?

一定是选最小的,所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        //你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯:初始化dp[0] = 0,dp[1] = 0;
        //可选择向上爬一个或者两个台阶可以有两个途径得到dp[i],一个是dp[i-1] 一个是dp[i-2](一个台阶前或两个台阶前)

        //1.确定dp数组(dp table)以及下标的含义: dp[i]:到达第i台阶所花费的最少体力为dp[i]
        int n=cost.length;
        int[] dp=new int[n+1];
        //2.确定递推公式:dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        //3.dp数组如何初始化:dp[0]=0,dp[1]=0
        dp[0]=0;
        dp[1]=0;
        //4.确定遍历顺序:从前向后
        for(int i=2;i<=n;i++){
            dp[i]=Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        //5.举例推导dp数组
        return dp[n];
    }
}

 

 

标签:下标,上爬,台阶,746,int,力扣,cost,爬楼梯,dp
From: https://www.cnblogs.com/cjhtxdy/p/17146238.html

相关文章

  • 【力扣】:N字型
    1classSolution{2publicStringconvert(Strings,intnumRows){3StringresultS="";//待返回的字符串4intlen......
  • 力扣days02 链表
    力扣203.移除链表元素力扣707.设计链表已经覆盖了链表的常见操作,是练习链表操作非常好的一道题目;力扣206.反转链表再定义一个新的链表,实现链表元素的反转,是......
  • 力扣239
    力扣239.滑动窗口最大值问题题目描述给定一个数组nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口......
  • 力扣538 把二叉搜索树转换为累加树
    题目:给出二叉搜索树的根节点,该树的节点值各不相同,请你将其转换为累加树(GreaterSumTree),使每个节点node的新值等于原树中大于或等于node.val的值之和。提醒一下,二叉......
  • 力扣:最长回文
    classSolution{publicStringlongestPalindrome(Strings){intmax=1;//设置回文字符串长度为1intlen=s.length();//设置......
  • 力扣108 将有序数组转换为二叉搜索树
    题目:给你一个整数数组nums,其中元素已经按升序排列,请你将其转换为一棵高度平衡二叉搜索树。高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值......
  • 力扣---22. 括号生成
    数字n代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且有效的括号组合。示例1:输入:n=3输出:["((()))","(()())","(())()","()(())","()()()"]示例2:输......
  • 力扣450 删除二叉搜索树中的节点
    题目:给定一个二叉搜索树的根节点root和一个值key,删除二叉搜索树中的key对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。一般......
  • 力扣中189 轮转数组
    开新数组移动克隆数组:     publicstaticvoidrotate(int[]nums,intk){//int[]numstemp=nums;//这么写会指向同一片内存导致出错int......
  • 力扣简2347 最好的扑克手牌
    暴力求解但是忽略了三条中的2=3=4的情况后面写着写着想了想可以构建一个数组又觉得占内存还是暴力解了publicstaticStringbestHand(int[]ranks,char[]su......