LeetCode 75 Level 1 - Day 11 Dynamic Programming

746. Min Cost Climbing Stairs

• 題目連結
• 難易度：Easy

題目敘述

You are given an integer array where is the cost of step on a staircase. Once you pay the cost, you can either climb one or two steps..
You can either start from the step with index 0, or the step with index 1.
Return the minimum cost to reach the top of the floor.

預設函數

int minCostClimbingStairs(int* cost, int costSize){

}

題目限制

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

解題過程及程式碼

本題是 Dynamic Programming的第三題，跟[70. Climbing Stairs]一樣給了一個n階樓梯，但也給一個陣列代表你在每一階代價來繼續前進，一開始可以選擇從0階出發也可以從1階出發，之後每一步都可以選擇一次走一階或一次走二階 (只要你付出了陣列裡該階的代價)，最後需要求出最小的代價來爬到最高階，初見時真是沒有想法，於是參考網路上的做法[LeetCode] 746. Min Cost Climbing Stairs 爬楼梯的最小损失，說明如下：

• dp[i] -> 爬到第[ i ]階的最小花費，例如題目總共有3階(index = 0、1、2)的話，所求就是 dp[3]。
• cost[i] -> 代表踩到第[ i ]階後要繼續前進的花費，要踩到第3階的方法就是先踩上第2階或第1階，接著找出最小花費dp[3] = MIN(dp[2] + cost[2], dp[1] + cost[1])。
• 一開始可以選擇從0或1出發，於是 dp[0] = 0、dp[1] = 0。

程式碼上傳

#define MIN(x, y) (((x) < (y)) ? (x) : (y))

int minCostClimbingStairs(int* cost, int costSize){

    int dp[1001] = {0};

    dp[0] = 0;
    dp[1] = 0;

    for (int i=2; i<costSize+1; i++) {
        dp[i] = MIN(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]);
    }
    return dp[costSize];
}

第21天的旅程先到這裡，謝謝大家!