LWC 63:746. Min Cost Climbing Stairs

Problem:

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed). Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:

Input: cost = [10, 15, 20] Output: 15 Explanation: Cheapest is start on cost1, pay that cost and go to the top.

Example 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] Output: 6 Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Note:

cost will have a length in the range [2, 1000].

Every cost[i] will be an integer in the range [0, 999].

思路: 好吧,此题所说的跳到top指的是跳到数组末尾的下一个位置。动态规划,记录当前位置所需要花费的最小代价,要么从前一个位置来,要么从前两个位置来,代码如下:

Java版本:

    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 16];
        for (int i = 2; i <= n; ++i) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }

Python版本:

    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        n = len(cost)
        dp = [0] * (n + 1)
        for i in xrange(2, n + 1):
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

        return dp[n]

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Albert陈凯

TimeUtil类所有方法

TimeUtil类的方法.png public static final String DATE_FORMAT = "yyyy-MM-dd"; /** ...

3486
来自专栏数据结构与算法

17:字符串判等

17:字符串判等 总时间限制: 1000ms 内存限制: 65536kB描述 判断两个由大小写字母和空格组成的字符串在忽略大小写,且忽略空格后是否相等。 ...

3759
来自专栏Java帮帮-微信公众号-技术文章全总结

第十三天 面向对象-final static 匿名对象内部类包代码块【悟空教程】

1474
来自专栏chenjx85的技术专栏

leetcode-686-Repeated String Match(重复多少次A能够找到B)

1453
来自专栏orientlu

读 《C Traps and Pitfalls》Record

单引号实际代表一个整数 双引号代表指向无名数组的起始字符的指针(字符结尾 0) 使用库函数计算得到的字符串长度不包括结尾的0!

1153
来自专栏nnngu

Java中的String类能否被继承?为什么?

不能被继承,因为String类有final修饰符,而final修饰的类是不能被继承的。 Java对String类的定义: public final class ...

4556
来自专栏大数据钻研

JavaScript 知识点整理

JavaScript是按照ECMAScript标准设计和实现的,后文说的JavaScript语法其实是ES5的标准的实现。 先说说有哪些基础语法? 最基础语法有...

2245
来自专栏JetpropelledSnake

Python学习笔记之Python正则表达式指南

正则表达式并不是Python的一部分。正则表达式是用于处理字符串的强大工具,拥有自己独特的语法以及一个独立的处理引擎,效率上可能不如str自带的方法,但功能十分...

2081
来自专栏于晓飞的专栏

Java 泛型进阶

在 List<String> 中添加 Integer 将不会通过编译,但是List<Sring>与List<Integer>在运行时的确是同一种类型。

2183
来自专栏开发与安全

从零开始学C++之从C到C++(一):const与#define、结构体对齐、函数重载name mangling、new/delete 等

一、bool 类型 逻辑型也称布尔型,其取值为true(逻辑真)和false(逻辑假),存储字节数在不同编译系统中可能有所不同,VC++中为1个字节。 声明方式...

1940

扫码关注云+社区

领取腾讯云代金券