1、要能够分析出递归的表达式是解决这个问题的前提。
2、将递归问题转化为循环形式的动态规划问题，减少重叠子问题的计算。

Question

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

提示：0 <= num < 231

测试用例

功能测试（只有一位数字；包含多位数字）。 特殊输入测试（负数；0；包含25、26的数字）。

本题考点

考查应聘者分析问题的能力。应聘者能够问题中分析出递归的表达式是解决这个问题的前提。 考查应聘者对递归及时间效率的理解。如果只是能够把递归分析转换为递归代码，则应聘者不一定能够通过这道题的面试。面试官期待应聘者能够用基于循环的代码来避免不必要的重复计算。

Intuition

我们以12258为例分析如何从数字的第一位开始一步步计算不同翻译方法的数目。我们有两种不同的选择来翻译第一位数字1。第一种选择是数字1单独翻译成“b”，后面剩下数字2258；第二种选择是1和紧挨着的2一起翻译成“m”，后面剩下数字258。

当最开始的一个或者两个数字被翻译成一个字符之后，我们接着翻译后面剩下的数字。显然，我们可以写一个递归函数来计算翻译的数目。我们定义函数 \(f(i)\) 表示从第i位数字开始的不同翻译的数目，那么 \[ f(i) = f(i+1) + g(i，i+1) \times f(i+2) \] 当第 \(i\) 位和第 \(i+1\) 位两位数字拼接起来的数字在10~25的范围内时，函数 $ g(i，i+1)$ 的值为1；否则为0。尽管我们用递归的思路来分析这个问题，但由于存在重复的子问题，递归并不是解决这个问题的最佳方法。还是以12258为例。如前所述，翻译12258可以分解成两个子问题：翻译1和2258，以及翻译12和258。接下来我们翻译第一个子问题中剩下的2258，同样也可以分解成两个自问题：翻译2和258，以及翻译22和58。注意到子问题翻译258重复出现了。

既然有重叠子问题出现，满足以下条件： 1. 该问题要求最优解。 2. 整体问题的最优解是依赖各个子问题的最优解。 3. 子问题之间还有相互重叠的更小的子问题。 4. 该问题适用于从上往下分析问题，从下往上求解问题的 解决思路。

就可以处理成基于动态规划的循环问题了，这样时间复杂度更小。换而言之，从数字的末尾开始，然后从右到左翻译并计算不同翻译的数目。

从后往前遍历，状态转移方程为：

if 9 < nums[i] * 10 + nums[i+1] < 26:  # 凑齐了两位数 10~25 又多一种翻译方法
    dp[i] = dp[i+1] + dp[i+2]
else:
    dp[i] = dp[i+1]

Python Code

class Solution:
    def translateNum(self, num: int) -> int:
        # 特殊处理 count<3的情况
        if num < 10:
            return 1
        if 9 < num < 99:
            return 2 if 9 < num < 26 else 1

        # 将int转成list
        count = 0
        nums = []
        while num:
            nums.append(num%10)
            count += 1
            num //= 10

        # count>=3的情况
        nums.reverse()
        dp = [1 for _ in range(count)]
        dp[-1] = 1
        dp[-2] = 2 if 9 < nums[-2] * 10 + nums[-1] < 26 else 1
        for i in range(count-3, -1, -1):
            if 9 < nums[i] * 10 + nums[i+1] < 26:
                dp[i] = dp[i+1] + dp[i+2]
            else:
                dp[i] = dp[i+1]
        return dp[0]

Java Code

class Solution {
    public int translateNum(int num) {
        String src = String.valueOf(num);
        int p = 0, q = 0, r = 1;
        for (int i = 0; i < src.length(); ++i) {
            p = q; 
            q = r; 
            r = 0;
            r += q;
            if (i == 0) {
                continue;
            }
            String pre = src.substring(i - 1, i + 1);
            if (pre.compareTo("25") <= 0 && pre.compareTo("10") >= 0) {
                r += p;
            }
        }
        return r;
    }
}