LeetCode Note Java 00746：Min Cost Climbing Stairs

情境題：付費爬樓梯，每階價格不同，每步走一階或兩階，求最便宜登頂價格。

題目

Min Cost Climbing Stairs Easy

You are given an integer array cost where cost[i] is the cost of ith 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.

解法

• 一維動態規劃：到達每一階最便宜的價格
• 只可能從前一階或前前一階上來

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        for (int i = 2; i < cost.length; i++) {
          cost[i] += Math.min(cost[i - 1], cost[i - 2]);
        }
        return Math.min(cost[cost.length - 1], cost[cost.length - 2]);
    }
}

動態規劃的規律都不太好想，只能多練培養直覺。