今天這題的題目描述是: (Problem Description)給你一個整數數組 cost，其中 $cost[i]$ 是從樓梯第 $i$ 個台階向上爬需要支付的費用。一旦你支付此費用，即可選擇向上爬一個或兩個台階。你可以選擇從下標為 $0$ 或下標為 $1$ 的台階開始爬樓梯。請你計算並返回達到樓梯頂部的最低花費。

約束條件：樓梯頂部在數組的末尾之後，即到達第 $n$ 階。

class Solution {
    /**
     * LeetCode 746: Min Cost Climbing Stairs
     * 使用動態規劃求解達到樓梯頂部的最低花費。
     * DP[i] 定義為到達第 i 階時的最小累計花費（已包含 cost[i]）。
     * 最終結果是 min(DP[n-1], DP[n-2])，因為頂部沒有成本。
     * * @param cost 每個台階的費用數組
     * @return 達到樓梯頂部的最低花費
     */
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        
        // 由於我們只需要 DP[i-1] 和 DP[i-2]，可以使用 O(1) 空間優化
        
        // DP[i-2]，代表到達第 i-2 階的最小花費（已支付 cost[i-2]）
        int dp_prev_prev = cost[0]; 
        // DP[i-1]，代表到達第 i-1 階的最小花費（已支付 cost[i-1]）
        int dp_prev = cost[1];
        
        // 從 i=2 開始計算，一直到 n-1 階
        for (int i = 2; i < n; i++) {
            // DP[i] = min(DP[i-1], DP[i-2]) + cost[i]
            
            // 選擇從前一階或前兩階上來，並加上當前階 i 的費用
            int dp_current = Math.min(dp_prev, dp_prev_prev) + cost[i];
            
            // 更新狀態
            dp_prev_prev = dp_prev; // 將 DP[i-1] 變成下一次的 DP[i-2]
            dp_prev = dp_current;   // 將 DP[i] 變成下一次的 DP[i-1]
        }
        
        // 樓梯頂部（n 階）可以從 n-1 階或 n-2 階到達。
        // 到達頂部不需要支付額外的 cost，所以結果是 min(DP[n-1], DP[n-2])。
        // 由於迴圈結束時，dp_prev_prev 是 DP[n-2]，dp_prev 是 DP[n-1]，
        // 我們直接比較這兩個值即可。
        return Math.min(dp_prev, dp_prev_prev);
    }
}