专栏首页前端小书童【一天一大 lee】使用最小花费爬楼梯 (难度:简单) - Day20201221

【一天一大 lee】使用最小花费爬楼梯 (难度:简单) - Day20201221

20201221

题目:

数组的每个索引作为一个阶梯,第 i 个阶梯对应着一个非负数的体力花费值 cost[i] ,(索引从 0 开始)。

每当你爬上一个阶梯你都要花费对应的体力花费值,然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时,你可以选择从索引为 0 或 1 的元素作为初始阶梯。

示例:

  1. 示例 1:
输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始,然后走两步即可到阶梯顶,一共花费15。
  1. 示例 2:
输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始,逐个经过那些1,跳过cost[3],一共花费6。

注意:

  • cost 的长度将会在 [2, 1000]。
  • 每一个 cost[i] 将会是一个 Integer 类型,范围为 [0, 999]。

抛砖引玉

一个数组,索引 index 从 0 或者 1 开始,每次递增 1 或者 2,求 index 经过的元素和最小是多少

第一反应应该就是:每次两个数中取较小的数

再仔细一想,前面的选择后影响后面两个比较的数到底是什么,那么需要动态的看到 index 的变化:比较的两个数依赖前一次的选,设 dp[i]为指针能到达 n 时(此时 index 可能在 i-1 或者 i-2 处)的最小和:

  • 走到 i-1:dp[i-1] + cost[i - 1]
  • 走到 i-2:dp[i-2] + cost[i - 2]

dp[i] = Math.min(dp[i-1] + cost[i - 1],dp[i-2] + cost[i - 2])

抛砖引玉

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    const n = cost.length
    const dp = new Array(n + 1)
    dp[0] = dp[1] = 0
    for (let i = 2; i <= n; i++) {
        dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
    }
    return dp[n]
}

简化

从上面可以看出 dp[i]只依赖 dp[i-1]、dp[i-2],则可以声明两个变量来记录 dp[i]依赖的 index 路径

var minCostClimbingStairs = function(cost) {
    const n = cost.length
    let prevNum = 0,
        indexNum = 0
    for (let i = 2; i <= n; i++) {
        let next = Math.min(indexNum + cost[i - 1], prevNum + cost[i - 2])
        prevNum = indexNum
        indexNum = next
    }
    return indexNum
}

博客: 前端小书童

每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言

公众号:前端小书童

本文分享自微信公众号 - 前端小书童(gaowenju_web),作者:前端小书童

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-12-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一天一大 leet(爬楼梯)难度:简单 DAY-13

    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

    前端小书童
  • leetcode 每日一题:746. 使用最小花费爬楼梯

    leetcode 每日一题:746. 使用最小花费爬楼梯:https://leetcode-cn.com/problems/min-cost-climbing-...

    用户7685359
  • 动态规划:使用最小花费爬楼梯

    题目链接:https://leetcode-cn.com/problems/min-cost-climbing-stairs/

    代码随想录
  • 【一天一大 lee】二叉搜索树的最小绝对差 (难度:简单) - Day20201012

    给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。

    前端小书童
  • 力扣上的代码想在本地编译运行?

    其实在代码随想录刷题群里也经常出现这个场景,就是录友发一段代码上来,问大家这个代码怎么有问题?如果我看到了一般我的回复都是:把那几个变量或者数组打印一下看看对不...

    代码随想录
  • LeetCode 746. 使用最小花费爬楼梯

    https://leetcode-cn.com/problems/min-cost-climbing-stairs/

    freesan44
  • 打卡群2刷题总结1014——爬楼梯

    https://leetcode-cn.com/problems/climbing-stairs/

    木又AI帮
  • 养老机器人能拯救“老龄中国”吗?

    “操作的时候你上身保持平衡,下压手柄60度,找准重心,几乎就不需要用力了。” 在上海浦东新区的金杨敬老院内,锝茂信息科技有限公司副总经理孙旭东正在亲自为护...

    机器人网
  • IT人必读的10个小故事

    1.从前,有两个饥饿的人得到了一位长者的恩赐:一根鱼竿和一篓鲜活硕大的鱼。其中, 一个人要了一篓鱼,另一个人要了一根鱼竿,于是他们分道扬镳了。得到鱼的人原地就用...

    李海彬
  • IT人必读的10个小故事

    1.从前,有两个饥饿的人得到了一位长者的恩赐:一根鱼竿和一篓鲜活硕大的鱼。其中, 一个人要了一篓鱼,另一个人要了一根鱼竿,于是他们分道扬镳了。得到鱼的人原地就用...

    李海彬
  • 【每日leetcode】6.爬楼梯

    一条coding
  • 摄像头、雷达、地图都不用,双足机器人走路全靠「我觉得」

    双足机器人昂贵、复杂且易碎。单从平衡性来看,双脚站立和行走要比四足难得多,但由于双足机器人更像人,仍然有许多研究者致力于研发双足机器人。

    机器之心
  • 【真相】DARPA机器人挑战赛的机器人并没有那么差

    上周末,我去加州波莫纳参加2015DARPA机器人挑战赛总决赛,这场挑战赛的主要是机器人(通常是人形机器人)面对各种灾难和救援任务的竞争。本次大赛受到了新闻媒体...

    机器人网
  • 尾递归优化原理与Python实现(以Fibonacci数列和小明爬楼梯问题为例)

    众所周知,在函数递归调用时,要保存函数调用的位置以便使得被调函数结束后能够返回正确的位置,这个信息保存在线程栈中。由于栈的空间有限,所以如果函数递归调用深度超过...

    Python小屋屋主
  • 算法-爬楼梯 2

    一个小孩爬一个 n 层台阶的楼梯。他可以每次跳 1 步, 2 步 或者 3 步。实现一个方法来统计总共有多少种不同的方式爬到最顶层的台阶

    OBKoro1
  • 10道最高频的手撕代码题都会了吗?(Python版)

    相信我,彻底掌握以下这10道题的解法,你顺利做出手撕代码面试题目的概率至少不低于50%。

    程序IT圈
  • 为了应对双11购物狂潮,各大公司都祭出了哪些黑科技?

    面对即将到来的双11购物狂潮,小伙伴们最担心的恐怕不是优惠力度不够,或者是钱包有点瘪,而是买买买之后,要经过多长时间的漫长等待,才能拿到自己的宝贝呢?为了加速整...

    机器人网
  • 想去看机会?这10道最高频的手撕代码题都会了吗?

    相信我,彻底掌握以下这10道题的解法,你顺利做出手撕代码面试题目的概率至少不低于50%。

    石晓文
  • 想去看机会?这10道最高频的手撕代码题都会了吗?

    相信我,彻底掌握以下这10道题的解法,你顺利做出手撕代码面试题目的概率至少不低于50%。

    lyhue1991

扫码关注云+社区

领取腾讯云代金券