746. Min Cost Climbing Stairs - Easy

前往題目

思路

1. 從尾端開始，頂端需要0，最後一個台階需要至少本身的cost
2. 倒數第二個台階需要本身的cost，再加上最後一個台階和頂端的最小值
3. 以此類推可以得出: dp[i] = cost[i] + Math.min(dp[i + 1], dp[i + 2])

需要O(N)空間

其實也可以不用dp陣列，用原本的cost陣列就好，因為要不就是bottom up，要不就是top down，都是一步一步建立起來的解，所以之前的值被改變無所謂

Code

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1]; // Including the top
        // The top
        dp[dp.length - 1] = 0;
        // The last cost
        dp[dp.length - 2] = cost[cost.length - 1];

        // Start from the second cost from behind
        for (int i = cost.length - 2; i >= 0; --i) {
            // Current mim cost is the current cost + the minimum of the next 1 step and 2 steps cost
            dp[i] = cost[i] + Math.min(dp[i + 1], dp[i + 2]);
        }

        // Decide starting from 0 or 1
        return Math.min(dp[0], dp[1]);
    }
}

O(1)空間優化

class Solution {
    public int minCostClimbingStairs(int[] cost) {

        // Start from the third cost from behind
        for (int i = cost.length - 3; i >= 0; --i) {
            // Current mim cost is the current cost + the minimum of the next 1 step and 2 steps cost
            cost[i] = cost[i] + Math.min(cost[i + 1], cost[i + 2]);
        }

        // Decide starting from 0 or 1
        return Math.min(cost[0], cost[1]);
    }
}