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

相关文章

来自专栏专注 Java 基础分享

从源码看集合ArrayList

     可能大家都知道,java中的ArrayList类,是一个泛型集合类,可以存储指定类型的数据集合,也知道可以使用get(index)方法通过索引来获...

1746
来自专栏Bingo的深度学习杂货店

Q402 Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from t...

692
来自专栏尾尾部落

[LeetCode]Longest Continuous Increasing Subsequence 最长连续增长序列 [LeetCode]Longest Continuous Incr

链接:https://leetcode.com/problems/longest-continuous-increasing-subsequence/descr...

471
来自专栏我是业余自学C/C++的

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unkonwn to you beforehand. (i.e...

835
来自专栏余林丰

有关ArrayList常用方法的源码解析

jdk1.7.0_79   我相信几乎所有的同学在大大小小的笔试、面试过程中都会被问及ArrayList与LinkedList之间的异同点。稍有准备的人这些问...

2007
来自专栏Bingo的深度学习杂货店

Q101 Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric aroun...

3138
来自专栏专注研发

poj-1056-IMMEDIATE DECODABILITY(字典)

An encoding of a set of symbols is said to be immediately decodable if no code f...

581
来自专栏计算机视觉与深度学习基础

Leetcode 215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth larg...

18010
来自专栏机器学习入门

LWC 58:724. Find Pivot Index

LWC 58:724. Find Pivot Index 传送门:724. Find Pivot Index Problem: Given an array ...

1788
来自专栏我是业余自学C/C++的

Remove Duplicates from Sorted Array II

1434

扫码关注云+社区