LeetCode 91 解碼方法：動態規劃 O(n) 時間 O(1) 空間完美解法

問題重述

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

狀態定義與轉移

dp[i] = 前 i 個字符的解碼數。
考慮第 i 位（1-indexed）：
1. 單獨解碼：若 s[i] != '0'，dp[i] += dp[i-1]。
2. 合併解碼：若 s[i-1..i] 在 "10".."26" 之間，dp[i] += dp[i-2]。

空間優化：滾動變量

只依賴前兩狀態，用 pre(dp[i-2])、cur(dp[i-1]) 迭代。
邊界：pre=1（空串 1 種），cur=1（首字符非 0 時）。

完整代碼

int numDecodings(string s) {
    if (s.empty() || s[0]=='0') return 0;
    int n = s.size();
    int pre = 1, cur = 1;
    for (int i = 1; i < n; ++i) {
        int tmp = 0;
        if (s[i] != '0') tmp += cur;
        int val = (s[i-1]-'0')*10 + (s[i]-'0');
        if (val >= 10 && val <= 26) tmp += pre;
        pre = cur; cur = tmp;
        if (cur == 0) return 0; // 提前剪枝
    }
    return cur;
}

關鍵邊界處理

• 字符串以 '0' 開頭 → 0。
• 連續 '0' 或 '30'、'40' 等無效雙位數 → 0。
• 單字符串直接返回 1（非 '0'）。

遞歸 + 備忘錄寫法（教學用）

int dfs(int i) {
    if (i == n) return 1;
    if (s[i]=='0') return 0;
    if (memo[i]!=-1) return memo[i];
    int ans = dfs(i+1);
    if (i+1