leetcode 746 Min Cost Climbing Stairs

fyber 發布于2019-08-16 11:01 / 420人閱讀

摘要：同時你可以選擇從第階開始或者第一階開始。我們的目標是找出你爬到最頂層所付出的最小的開銷。最低開銷是，從第階開始，只花費就可以到頂層。想法動態規劃問題。的長度應該為數組長度加一，其中數組的最后一個元素的值就是本題的答案，最低開銷。

題目詳情

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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