动态规划--最小代价爬楼梯

Myth丶恋晨 2022-05-23 07:46 171阅读 0赞

1、题目：

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 cost[1], 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:

1.  `cost` will have a length in the range `[2, 1000]`.
2.  Every `cost[i]` will be an integer in the range `[0, 999]`.

2、解答：自下而上的解答，先求出第2个的最小值，然后依次类推

3、代码：

python 代码

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

C++代码

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

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划之使用最小花费爬楼梯

1. 题目分析题目链接选自力扣 : [使用最小花费爬楼梯][Link 1] ![image.png][] 先根据示例 1 来理解一下题目的意思. ![ima

「爱情、让人受尽委屈。」/ 2024年03月16日 22:01/ 0 赞/ 15 阅读

相关利用动态规划求解爬楼梯问题

题目描述：假设你正在爬楼梯，需要n阶才能到达楼顶。每次可以爬1或2阶，你有多少种不同的方法可以爬到楼顶呢？其中n是一个正整数。思路和算法：利用动态规划，用f

约定不等于承诺〃/ 2022年12月28日 05:30/ 0 赞/ 127 阅读

相关【必备算法】动态规划：LeetCode题（一）：70.爬楼梯，746. 使用最小花费爬楼梯

[70.爬楼梯¹][70.] 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n

Dear 丶/ 2022年12月16日 13:25/ 0 赞/ 163 阅读

相关算法题目——使用最小花费爬楼梯(动态规划)

题目链接：[746.使用最小花费爬楼梯][746.] 方法:动态规划假设数组cost的长度为n,则n个阶梯分别对应下标0到n- 1,楼层顶部对应下标n,问题等价于计算达到

我会带着你远行/ 2022年09月14日 11:16/ 0 赞/ 139 阅读

相关算法题目——爬楼梯(动态规划)

题目链接：[70.爬楼梯][70.] 类似题目：[1646.获取生成数组中最大值][1646.] ![在这里插入图片描述][watermark_type_ZHJvaWRz

╰+哭是因爲堅強的太久メ/ 2022年09月14日 11:14/ 0 赞/ 164 阅读

相关最小编辑代价（动态规划）

![20151205205631477][] 代码实现：对于不同的要求，主要是找到求dp\[i\]\[j\]的规律。 include <iostre

深藏阁楼爱情的钟/ 2022年08月18日 02:19/ 0 赞/ 156 阅读

相关动态规划--爬楼梯

1、题目： You are climbing a stair case. It takes n steps to reach to the top. Each time y

心已赠人/ 2022年05月23日 07:47/ 0 赞/ 154 阅读

相关动态规划--最小代价爬楼梯

1、题目： On a staircase, the `i`\-th step has some non-negative cost `cost[i]` assigned (0

Myth丶恋晨/ 2022年05月23日 07:46/ 0 赞/ 172 阅读

相关 [算法提高] 动态规划爬楼梯

\[问题背景\] 来源：LeetCode(力扣) 编号：[70. 爬楼梯][70.] 内容：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或

喜欢ヅ旅行/ 2022年03月06日 04:03/ 0 赞/ 183 阅读

相关 [动态规划] 70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。超出时

约定不等于承诺〃/ 2021年12月09日 00:19/ 0 赞/ 220 阅读