成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode 746 Min Cost Climbing Stairs

fyber / 427人閱讀

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

題目詳情 
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. 
給定一個數(shù)組cost，其中cost[i]的值就代表著你爬第[i]階的臺階的開銷。一旦你付了這個開銷，你就可以繼續(xù)往上爬一階或者兩階，知道你達到最頂層（數(shù)組的結(jié)尾元素再多一層）。同時你可以選擇從第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階。
想法

動態(tài)規(guī)劃問題。

我們新建一個數(shù)組minCost，用它來保存走到第i階所消耗的最低開銷。

minCost的長度應該為cost數(shù)組長度加一，其中mincost數(shù)組的最后一個元素的值就是本題的答案，最低開銷。

解法 
    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];
    }

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/70918.html

相關(guān)文章

  • 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 評論0 收藏0

  • 前端 | 每天一個 LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

    張漢慶 評論0 收藏0

  • [Leetcode] Climbing Stairs 爬樓梯

    摘要：遞歸法復雜度時間空間思路這題幾乎就是求解斐波那契數(shù)列。最簡單的方法就是遞歸。但重復計算時間復雜度高。代碼遞推法復雜度時間空間思路實際上我們求的時候只需要和的值，所以可以減少一些空間啊。 Climbing Stairs You are climbing a stair case. It takes n steps to reach to the top. Each time you c...

    tinyq 評論0 收藏0

  • [leetcode] Climbing Stairs

    摘要：實質(zhì)就是把之前出現(xiàn)過的中間結(jié)果記錄，下次再出現(xiàn)相同情況的時候，通過可以只用的時間復雜度得到。表示到達第層樓梯的不同走法。那么題目中每次可以選擇走一步，或者兩步，。從迭代公式可以知道，有兩個，和。 70. Climbing Stairs You are climbing a staircase. It takes n steps to reach to the top.Each tim...

    int64 評論0 收藏0

  • leetcode70 climbing stairs 爬樓梯游戲

    摘要：題目要求假設(shè)有級臺階為正整數(shù)，每次可以爬一級臺階或兩級臺階。問有多少種方法爬完級臺階遞歸方法最后一步可以是一級臺階，或者是兩級臺階，一共兩種情況。 題目要求：假設(shè)有n級臺階（n為正整數(shù)），每次可以爬一級臺階或兩級臺階。問有多少種方法爬完n級臺階？ 遞歸方法最后一步可以是一級臺階，或者是兩級臺階，一共兩種情況。可通過遞歸獲得n-1級臺階和n-2級臺階的和獲得n級臺階的結(jié)果臺階數(shù)量過高的話...

    姘存按 評論0 收藏0

發(fā)表評論

0條評論

fyber

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<