LeetCode 解碼方法：動態規劃從後向前計算解碼數

題目描述

映射：'1'->'A', ..., '26'->'Z'。給定數字字符串，返回解碼方法總數。無效編碼（如 '0' 開頭）返回 0。

動態規劃（從後向前）

定義 dp[i] 為子串 s[i:] 的解碼數。
dp[n] = 1（空串）。
若 s[i] == '0'，dp[i] = 0。
否則 dp[i] = dp[i+1]；若 i+1 < n 且 10 <= stoi(s.substr(i,2)) <= 26，則 dp[i] += dp[i+2]。
結果為 dp[0]。

代碼實現 (Python)

class Solution:
    def numDecodings(self, s):
        n = len(s)
        if n == 0: return 0
        dp = [0] * (n + 1)
        dp[n] = 1
        dp[n-1] = 1 if s[n-1] != '0' else 0
        for i in range(n-2, -1, -1):
            if s[i] != '0':
                dp[i] = dp[i+1]
                if int(s[i:i+2]) <= 26:
                    dp[i] += dp[i+2]
        return dp[0]

複雜度

• 時間：O(n)
• 空間：O(n)