专栏首页racaljkLeetcode 746. Min Cost Climbing Stairs 最小成本爬楼梯 (动态规划)

Leetcode 746. Min Cost Climbing Stairs 最小成本爬楼梯 (动态规划)

题目翻译

有一个楼梯,第i阶用cost[i](非负)表示成本。现在你需要支付这些成本,可以一次走两阶也可以走一阶。 问从地面或者第一阶出发,怎么走成本最小。

测试样例

Input: cost = [10, 15, 20]
Output: 15
Explanation: 从第一阶出发,一次走两步

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: 从地面出发,走两步,走两步,走两步,走一步,走两步,走一步。

详细分析

现在用step[i]表示走到第i阶的成本,要求step[i],我们只需在"到前一阶的成本+当前阶成本"和"到前两阶的成本+前两阶成本"取最小即可。一图胜千言:

因为step[0]和step[1]都可以作为开始出发地,所以成本都为0。注意一下爬两阶只需要那两阶的第一个成本作为总成本不需要两阶成本相加。所以

step[2] = min{step[1]+cost[1],step[0]+cost[0]} = min{10,15}=10

step[3] = min{step[2]+cost[2],step[1]+cost[1]} = min{30,15} = 15

代码实现

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        if(cost.size()==0){
            return 0;
        }
        if(cost.size()==1){
            return cost[0];
        }
        if(cost.size()==2){
            return std::min(cost[0],cost[1]);
        }
        int step[1024];
        step[0] = 0;
        step[1] = 0;
        for(int i=2;i<=cost.size();i++){
            step[i] = std::min(step[i-1]+cost[i-1],step[i-2]+cost[i-2]);
        }
        return step[cost.size()];
    }
};

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 566. Reshape the Matrix 矩阵变形(数组,模拟,矩阵操作)

    在MATLAB中,reshape是一个非常有用的函数,它可以将矩阵变为另一种形状且保持数据不变。 已知一个由二维数组表示的矩阵,和两个正整数r(行),c(列)...

    racaljk
  • 如果将markdown视作一门编程语言可以做哪些有趣的事情?

    如题,然后就有了为解决这个好奇而开的项目:https://github.com/racaljk/llmd

    racaljk
  • Leetcode 8. String to Integer (atoi) atoi函数实现 (字符串)

    这道题的corner cases非常多,请务必确保下面cases都能通过的情况下再提交。

    racaljk
  • Python之Flake8 - Coding Style检查自动化的利器

    参考文档: http://blog.csdn.net/gaoyingju/article/details/50449522 http://fla...

    小小科
  • 【友盟+】COO叶谦:全域数据,智能未来

    <数据猿导读> 2016中国互联网大会全域大数据应用论坛于6月21日在北京国际会议中心举行。【友盟+】COO叶谦对全域数据智能驱动未来分享了自己的观点和看法。他...

    数据猿
  • Python2寿命只剩一个月啦!还不快赶紧学起Python3酷炫到爆的新特性!

    Python3.8已经发布了将近一个月了,距离Python3.0第一个版本发布也将超过10年了。相信很多人还是依旧在使用Python2.7版本,想要迁移到最新版...

    云爬虫技术研究笔记
  • 数据地图关系精细化分析

    元数据应用中对数据关系的分析,是元数据的核心能力,基于这项核心能力能够衍生出对诸多实际应用场景的支持,例如辅助数据运维,数据风险管控等。大部分组织实施元数据管理...

    yuanyi928
  • Android – 权限申请

    code_horse
  • 微信 Android 模块化架构重构实践(下)

    重构整体架构不是一件容易事,通常也不太可能让整个团队停下来只做重构。本文是微信 Android 模块化架构重构实践的下篇,主要分享模块化架构重构的一点点经验。

    微信终端开发团队
  • 动态地理信息可视化——散点地图系列

    这是一篇拖了好久的稿子,因为过年玩high了,一直放着没写,今天得空,赶快得空,赶紧整理一下。 本篇主讲leaflet在线地图系列中的散点系列,包含颜色映射规则...

    数据小磨坊

扫码关注云+社区

领取腾讯云代金券