剑指 Offer 46. 把数字翻译成字符串（动态规划）

题目描述

• 动态规划

使用 f ( n ) f(n) f(n)表示以当前第 n n n个数结尾的翻译个数，则有两种情况：

1. 若第 n n n个数与前一个数（ n − 1 n-1 n−1）组成的数≤25，则有一种新的组合方式；此外，当前这个数自身也是一种翻译方法。
2. 若第 n n n个数与前一个数（ n − 1 n-1 n−1）组成的数＞25，则只有当前这个数自身这一种翻译方法

故可以推出递推公式为
f ( n ) = { f ( n − 1 ) + f ( n − 2 ) , 情 形 1 f ( n − 1 ) , 情 形 2 f(n) = left{ begin{array}{lr} f(n-1) + f(n-2), 情形1 & \ f(n-1), 情形2 & end{array} right. f(n)={f(n−1)+f(n−2),情形1f(n−1),情形2​​

class Solution:
    def translateNum(self, num: int) -> int:
        # p, q, res = 0, 0, 0     # p表示f(n-1), q表示f(n-2)
        f = []
        num_str = str(num)
        for i, char in enumerate(num_str):
            if i == 0:
                f.append(1)
            elif i == 1:
                # int(num_str[i-1:i+1]) != int(char)是为了纠正错误判断类似'06'的情况
                if int(num_str[i-1:i+1]) <= 25 and int(num_str[i-1:i+1]) != int(char):
                    f.append(2)
                else:
                    f.append(1)
            elif int(num_str[i-1:i+1]) <= 25 and int(num_str[i-1:i+1]) != int(char):
                f.append(f[i-2] + f[i-1])
            else:
                f.append(f[i-1])
        return f[-1]

参考官方解法，可优化空间复杂度

class Solution:
    def translateNum(self, num: int) -> int:
        p, q, res = 0, 0, 1     # p表示f(n-2), q表示f(n-1)
        num_str = str(num)
        for i, char in enumerate(num_str):
            p = q
            q = res
            res = q
            # 如果是首位，则跳过
            if i == 0:
                continue
            t = int(num_str[i-1] + char)
            if t >= 10 and t <= 25:
                res += p
        return res