解題區►Leetcode►Easy

Leetcode 746 - Min Cost Climbing Stairs

題目

Problem#

給你一個整數陣列 cost[i] 代表踩第 i 階樓梯的花費，每次可以跨一階或是兩階，從 0 或是 1 開始踩，問到頂樓的最小花費是多少?

測資限制#

  • 樓梯階數: $2 \le n \le 1000$
  • cost 值: $0 \le val \le 999$

想法#

對於第 $i$ 階來說，要踩到這只可能來自於第 $i-1$ 或是 $i-2$ 階(因為一次只能踏 1 或 2 階)，所以可以得出公式:

$$
f(i)=
\begin{cases}
\min(f(i-1), f(i-2))+cost[i], & i \ge 2 \cr
cost[i], & i \le 1 \cr
\end{cases}
$$

接著應很容易可以照式子寫出程式。

AC Code#

這邊還有先將 cost 的前後都加上 0。前面的 0 是為了讓 cost 變成 1-index 的(個人習慣)
而後面的 0 是讓最後一階包含沒踩到的可能性(可能是從 n-1 踏兩階沒經過 n 到達 n+1[終點]的)
且因為兩個 cost 都是 0 所以也不影響答案，只是方便撰寫程式。

  • 時間複雜度: $\mathcal{O}(n)$
    • 從左往右根據公式去建立 dp 陣列
  • 空間複雜度: $\mathcal{O}(n)$
    • 儲存 dp 陣列

心得#

這題一開始是用 Top-Down 去思考並實作出來，結果在大測資 TLE 了，試著用 memo 但是失敗，改成 Bottom-up 就過了

TODO: top-down dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int n;
    vector<int> cost;

    int solve(int i, int c)
    {
        if(i+2 < n)
            return min(solve(i+1, c+cost[i+1]),
                       solve(i+2, c+cost[i+2]));
        else if(i+1 < n)
            return solve(i+1, c+cost[i+1]);
        else
            return c;
    }

    int minCostClimbingStairs(vector<int>& cost_)
    {
        cost = {0};
        cost.insert(cost.end(), cost_.begin(), cost_.end());
        cost.push_back(0);
        n = cost.size();
        
        return solve(0, 0);
    }
};