把数字翻译成字符串

把数字翻译成字符串_牛客题霸_牛客网

问题简述

有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。
现在给一串数字，返回有多少种可能的译码结果

思路：动态规划

• 有条件的“跳台阶”问题；

• 定义 dp(i) 表示 nums[i:] 的表示数；

• 则核心递推公式为： dp(i) = dp(i+1) + dp(i+2)；

• 易错点：nums[i] == 0 时，dp(i) == 0

Python 递归写法

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