leetcode 746 Min Cost Climbing Stairs

fyber 发布于2019-08-16 11:01 / 308人阅读

摘要：同时你可以选择从第阶开始或者第一阶开始。我们的目标是找出你爬到最顶层所付出的最小的开销。最低开销是，从第阶开始，只花费就可以到顶层。想法动态规划问题。的长度应该为数组长度加一，其中数组的最后一个元素的值就是本题的答案，最低开销。

题目详情

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.

给定一个数组cost，其中cost[i]的值就代表着你爬第[i]阶的台阶的开销。一旦你付了这个开销，你就可以继续往上爬一阶或者两阶，知道你达到最顶层（数组的结尾元素再多一层）。同时你可以选择从第0阶开始或者第一阶开始。
我们的目标是找出你爬到最顶层所付出的最小的开销。

Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: 最低开销是，从第1阶（15）开始，只花费15就可以到顶层。
Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: 最低开销是，从第0阶开始（1），然后只走值为1的台阶，其中跳过第3阶。

想法

动态规划问题。

我们新建一个数组minCost，用它来保存走到第i阶所消耗的最低开销。

minCost的长度应该为cost数组长度加一，其中mincost数组的最后一个元素的值就是本题的答案，最低开销。

解法

    public int minCostClimbingStairs(int[] cost) {
        int minCost[] = new int[cost.length+1];
        minCost[0] = cost[0];
        minCost[1] = cost[1];
                
        for(int i=2;i<=cost.length;i++){
            int costV = (i == cost.length) ? 0 : cost[i];
            minCost[i] = Math.min(minCost[i-1]+costV, minCost[i-2]+costV);
        }
        
        return minCost[cost.length];
    }

云服务器 GPU云服务器 Climbing Stairs Cost Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70918.html

746. Min Cost Climbing Stairs

746. Min Cost Climbing Stairs 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 mini...

skinner 2019-07-30 17:08 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
[Leetcode] Climbing Stairs 爬楼梯

摘要：递归法复杂度时间空间思路这题几乎就是求解斐波那契数列。最简单的方法就是递归。但重复计算时间复杂度高。代码递推法复杂度时间空间思路实际上我们求的时候只需要和的值，所以可以减少一些空间啊。 Climbing Stairs You are climbing a stair case. It takes n steps to reach to the top. Each time you c...

tinyq 2019-08-14 12:26 评论0 收藏0
[leetcode] Climbing Stairs

摘要：实质就是把之前出现过的中间结果记录，下次再出现相同情况的时候，通过可以只用的时间复杂度得到。表示到达第层楼梯的不同走法。那么题目中每次可以选择走一步，或者两步，。从迭代公式可以知道，有两个，和。 70. Climbing Stairs You are climbing a staircase. It takes n steps to reach to the top.Each tim...

int64 2019-08-14 16:50 评论0 收藏0
leetcode70 climbing stairs 爬楼梯游戏

摘要：题目要求假设有级台阶为正整数，每次可以爬一级台阶或两级台阶。问有多少种方法爬完级台阶递归方法最后一步可以是一级台阶，或者是两级台阶，一共两种情况。题目要求：假设有n级台阶（n为正整数），每次可以爬一级台阶或两级台阶。问有多少种方法爬完n级台阶？递归方法最后一步可以是一级台阶，或者是两级台阶，一共两种情况。可通过递归获得n-1级台阶和n-2级台阶的和获得n级台阶的结果台阶数量过高的话...

姘存按 2019-08-14 17:52 评论0 收藏0