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

相关文章

来自专栏机器学习入门

LWC 58:724. Find Pivot Index

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

1798
来自专栏wym

Educational Codeforces Round 44 (Rated for Div. 2)A. Chess Placing

You are given a chessboard of size 1 × n. It is guaranteed that n is even. The c...

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

Leetcode 55 Jump Game

Given an array of non-negative integers, you are initially positioned at the fi...

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

AtCoderBeginnerContest109题解

一开始读错题了,我以为移动几个都可以,事实上只能移动一个qwq,而且我以为0不统计入答案

321
来自专栏Golang语言社区

Go语言单链表实现方法

本文实例讲述了Go语言单链表实现方法。分享给大家供大家参考。具体如下: 1. singlechain.go代码如下: ////////// //单链表 -- 线...

3034
来自专栏小樱的经验随笔

Codeforces Round #434 (Div. 2, based on Technocup 2018 Elimination Round 1)&&Codeforces 861C Did yo

C. Did you mean... time limit per test:1 second memory limit per test:256 megaby...

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

1008 选数 2002年NOIP全国联赛普及组

1008 选数 2002年NOIP全国联赛普及组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 ...

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

BZOJ4939: [Ynoi2016]掉进兔子洞(莫队 bitset)

那么第$i$个询问的答案为$r1 - l1 + r2 - l2 + r3 - l3 + 3 - min(cnt1[x], cnt2[x], cnt3[x])$

541
来自专栏JackeyGao的博客

Leetcode 算法 - 1. Two Sum

这是我解的第一道题, 当时就懵比了, 写了若干方法均超时了. 最后到网上搜索的答案. 需要用哈希表, python 字典其实就是哈希表的实现. 感受下哈希表的使...

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

洛谷P3372 【模板】线段树 1(树状数组)

$= sum_{i = 1}^x (x+1)d_i - \sum_{i = 1}^x id_i$

1405

扫码关注云+社区