LeetCode Decode Ways：動態規劃計算解碼方法數

問題描述

數字字符串按 'A'→1, 'B'→2, ..., 'Z'→26 編碼。給定編碼字符串，求解碼方法總數。例："12" → "AB"(1,2) 或 "L"(12)，答案 2。

DP 狀態與轉移

dp[i] 表示前 i 個字符的解碼數（1-based）。

• 單字符解碼：若 s[i-1] != '0'，dp[i] += dp[i-1]。
• 雙字符解碼：若 i>=2 且 10 <= (s[i-2]-'0')*10 + (s[i-1]-'0') <= 26，dp[i] += dp[i-2]。
• 初始 dp[0]=1（空串 1 種），dp[1] 視首字符是否為 '0'。

代碼實現 (O(n) 時間, O(1) 空間)

int numDecodings(string s) {
    if (s.empty() || s[0]=='0') return 0;
    int n = s.size(), pre = 1, cur = 1;
    for (int i = 1; i < n; ++i) {
        int tmp = cur;
        if (s[i] == '0') cur = 0;
        if (s[i-1]=='1' || (s[i-1]=='2' && s[i]<='6')) cur += pre;
        pre = tmp;
        if (cur == 0) return 0; // 提前終止
    }
    return cur;
}

邊界情況處理

• 字符串以 '0' 開頭 → 0
• 連續 '0' 或 '30','40' 等無效雙字符 → 0
• 大數取模（題目無要求，但實際可加 MOD）