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 条评论
登录 后参与评论

相关文章

来自专栏大数据钻研

JavaScript 知识点整理

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

2055
来自专栏于晓飞的专栏

Java 泛型进阶

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

1493
来自专栏陈纪庚

Javasript设计模式之链式调用

而jquery这种调用方式就是链式调用。我们可以从上述代码看出来,如果不使用链式调用的话,那么我们会增加很多重复的代码,而且特别冗余。而通过链式调用,我们可...

921
来自专栏向治洪

Kotlin基础之内联函数

内联函数 使用高阶函数会给运行时带来一些坏处:每个函数都是一个对象,捕获闭包(如:访问函数体内的变量),内存分配(函数对象或Class),虚拟调用引入的运行过载...

1865
来自专栏orientlu

读 《C Traps and Pitfalls》Record

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

923
来自专栏超然的博客

ECMAScript 6 笔记(一)

       1996年11月,JavaScript的创造者Netscape公司,决定将JavaScript提交给国际标准化组织ECMA,希望这种语言能够成为国...

943
来自专栏用户2442861的专栏

python语法31[引用和拷贝]

  If an object’s value can be modified, the object is said to be mutable. If the...

511
来自专栏Albert陈凯

TimeUtil类所有方法

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

3386
来自专栏从零开始的linux

Python数据类型

整型 a=10 b=0 b+=a c=-100 c-=a print (a, b ,c) print (dir(a)) print (abs(a)+abs(c)...

2984
来自专栏CVer

排序算法 | 冒泡排序(含C++/Python代码实现)

排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。排序算法有很多,本文将介绍最经典的排序算法:冒泡排序...

862

扫码关注云+社区