题解 | #把数字翻译成字符串# 递归写法

欢迎star: imhuay/studies

贡献一种优雅的递归写法，当然本质上还是动态规划

class Solution:
    def solve(self , nums: str) -> int:
        
        n = len(nums)
        
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dfs(i):
            if i == n: return 1
            if nums[i] == '0': return 0
            r1 = dfs(i + 1)
            r2 = dfs(i + 2) if i < n - 1 and nums[i] == '1' else 0
            r3 = dfs(i + 2) if i < n - 1 and nums[i] == '2' and '0' <= nums[i + 1] <= '6' else 0
            return r1 + r2 + r3
        
        return dfs(0)