※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 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]
: 在這兩種情況取較小值就是當前的最小成本以此類推。
思路：
非常教科書式的dp題目
我就用dp陣列了
Code:
impl Solution {
pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
let n = cost.len();
let mut dp = vec![0; n];
dp[0] = cost[0];
dp[1] = cost[1];
for i in 2..cost.len() {
dp[i] = cost[i] + std::cmp::min(dp[i - 1], dp[i - 2]);
}
std::cmp::min(dp[n-1], dp[n-2])
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1697184666.A.AB3.html
※ 編輯: yam276 (60.248.143.163 臺灣), 10/13/2023 16:14:31