人森很精彩，所以要把所有事情都記起來=ˇ=

這題雖然是easy，不過我想了滿久的...

這是個爬階梯的遊戲，一次可以選擇爬一個或兩格

但是這邊會有一個陣列，決定你爬到那一階的時候要交多少錢

題目就是要找到花費最少的價錢，讓你可以爬完整段階梯

舉個例：

Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

題目應該不難理解吧，接著看解法吧

Sol：

最笨的方式，就是全部算出來

不過想當然那是不可能的，那還有什麼好解的...

我們就這樣想吧，如果爬到n階時的最少花費是c(n)，那這個c(n)會是多少呢

應該會是min(c(n-1), c(n-2))吧

關鍵就是這個啊，接下來就是看從前面算還是從後面算而已了

如果是從前面開始算的話，大概會長成這個樣子：

    int minCostClimbingStairs(vector<int>& cost) {
        int c1, c2 = 0;

        for (int i = 0; i < cost.size(); ++i)
        {
            int cur = min(c1, c2) + cost[i];
            
            c1 = c2;
            c2 = cur;
        }
        
        return min(c1, c2);
    }

應該不用多解釋了，就是一階一階往上算，直到最後兩階來比較哪個花費少就是答案

如果從後面開始算的話也行，就是從最上層開始往下走，code會長成這樣：

    int minCostClimbingStairs(vector<int>& cost) {
        int c1 = 0, c2 = 0;
        
        for (int i = cost.size() - 1; i >= 0; --i)
        {
            int cur = cost[i] + min(c1, c2);
            
            c2 = c1;
            c1 = cur;
        }
        
        return min(c1, c2);
    }

好啦其實是一樣的...

這個題目滿有趣的，可以好好品味一下

據說是有點Dinamic Programming的概念在，之後我也會貼幾題DP的題目上來

那這題就這樣了~