91. 解码方法

题目链接

解题思路：动态规划：从左往右的尝试模型，来到index位置，只解码index一个数，或者解码index和index+1两个数

代码

class Solution:

    # 只需要解码s[index...]即可
    def process(self, s: str, index: int, dp: List[int]) -> int:
        if index == len(s):   # 找到了一种有效解
            return 1 
        if s[index] == '0':   # 不是一种有效解
            return 0
        if dp[index] != -1:
            return dp[index]
        ans = 0
        # 单独一个数解码
        ans += self.process(s, index + 1, dp)
        # 两个数解码
        if index + 1 < len(s) and (int(s[index]) * 10 + int(s[index + 1])) <= 26:
            ans += self.process(s, index + 2, dp)
        dp[index] = ans
        return ans
    
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [-1 for _ in range(n)]
        ans = self.process(s, 0, dp)
        
        return ans