Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2023-10-13 12:26:16
https://leetcode.com/problems/min-cost-climbing-stairs/description
746. Min Cost Climbing Stairs
給你一個陣列 cost[] 表示每一層的成本,你需要爬樓梯到樓頂,你每次可以從當前
位置花費 cost[i] 走1步或2步,你從 0 或 1 出發,求出走到 cost.length 最小要
多少 cost。
思路:
1.動態規劃,位置 i 當前的成本只能是兩種情況:
* 往前一階的最小成本 + cost[i - 1]
* 往前兩階的最小成本 + cost[i - 2]
在這兩種情況取較小值就是當前的最小成本以此類推。
2.因為只需要用到 i - 2 之前的狀態,所以用額外兩個變數記錄就好。
Java Code:
作者: wwndbk (黑人問號)   2023-10-13 12:27:00
大師挖幹 java遞迴這麼簡單喔
作者: Rushia (みけねこ的鼻屎)   2023-10-13 12:28:00
這沒遞迴阿 迭代而已
作者: wwndbk (黑人問號)   2023-10-13 12:30:00
喔喔 看錯早上看題目以為這題會用到遞迴

Links booklink

Contact Us: admin [ a t ] ucptt.com