當然可以！LeetCode 746 是一道經典的動態規劃入門題，我來用 C++ 為你詳細解釋。

題目描述

給定一個整數數組 cost，其中每個元素 cost[i] 表示從第 i 個臺階向上爬需要支付的費用。一旦支付費用，你可以選擇向上爬 1 步 或 2 步。
你可以從下標 0 或 1 的臺階開始爬。
目標：計算到達樓梯頂部（即最后一個臺階之后）的最小總花費。

核心思路

1. 動態規劃定義：
   設 dp[i] 表示到達第 i 個臺階所需的最小總花費。
   最終答案：dp[n]，其中 n = cost.size()（即到達頂部的最小花費）。

2. 狀態轉移方程：
   到達第 i 個臺階的方式有兩種：

   • 從第 i-1 個臺階爬一步，總花費為 dp[i-1] + cost[i-1]。
   • 從第 i-2 個臺階爬兩步，總花費為 dp[i-2] + cost[i-2]。
     因此：

   dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
   

3. 初始條件：

   • dp[0] = 0：無需花費即可站在起點前。
   • dp[1] = 0：同理，可選擇從下標 0 或 1 開始，無需初始花費。

C++ 代碼實現

#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();if (n == 0) return 0;vector<int> dp(n + 1, 0);  // dp[i] 表示到達第 i 個臺階的最小花費// 初始化：站在起點前（0 或 1）不需要花費dp[0] = 0;dp[1] = 0;// 動態規劃計算for (int i = 2; i <= n; ++i) {dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);}return dp[n];  // 到達頂部（第 n 個臺階）的最小花費}
};

優化空間復雜度

由于 dp[i] 只依賴于 dp[i-1] 和 dp[i-2]，可以用兩個變量滾動優化：

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();if (n == 0) return 0;int prev2 = 0;  // 對應 dp[i-2]int prev1 = 0;  // 對應 dp[i-1]for (int i = 2; i <= n; ++i) {int current = min(prev1 + cost[i-1], prev2 + cost[i-2]);prev2 = prev1;prev1 = current;}return prev1;  // 對應 dp[n]}
};

示例解釋

輸入：cost = [10, 15, 20]

• dp[0] = 0
• dp[1] = 0
• dp[2] = min(dp[1] + 15, dp[0] + 10) = min(0 + 15, 0 + 10) = 10
• dp[3] = min(dp[2] + 20, dp[1] + 15) = min(10 + 20, 0 + 15) = 15
  輸出：15（從下標 1 開始，支付 15，直接跳兩步到頂部）

關鍵點總結

1. 動態規劃思想：用 dp 數組記錄到達每個臺階的最小花費。
2. 狀態轉移：當前狀態只依賴前兩個狀態，可用滾動數組優化空間。
3. 初始條件：起點前的位置無需花費。

這類問題是動態規劃的基礎，掌握后可輕松解決更復雜的路徑優化問題！