题目描述

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

题解

使用动态规划的方法，对于当前的数字，我们有两种选择：

1. 可以只翻译这个数字。
2. 将这个数字与前面一个数字一起翻译。

为了方便操作，将num的每一位数字存到字符数组chars中。假设当前数字是s[i]：

• 若当前数字与前一个数字的组合不在 10-25 之间，则翻译方法的总数就是s[0]到s[i-1]这个字符串翻译方法的数量。
• 若当前数字与前一个数字的组合在 10-25 之间时，在当前数字加入字符串之后，翻译方法的总数就是s[0]到s[i-1]字符串翻译方法的数量加上s[0]到s[i-2]字符串翻译方法的数量。

状态转移方程为：

边界条件为：

时间复杂度为，空间复杂度为。

public int translateNum(int num) {
    // 为了方便操作，将num的每一位数字存到字符数组chars中
    String s = String.valueOf(num);
    char[] chars = new char[s.length()+1];
    for (int i = 0; i < s.length(); i++)
        chars[i+1] = s.charAt(i);

    // dp[i] = dp[i-1]，若当前数字与前一个数字的组合不在10-25之间
    //       = dp[i-1] + dp[i-2]，若当前数字与前一个数字的组合在10-25之间
    int[] dp = new int[s.length()+1];
    dp[0] = 1;
    for (int i = 1; i < chars.length; i++) {
        dp[i] = dp[i-1];
        if (chars[i-1] == '1' || (chars[i-1] == '2' && chars[i] <= '5' && chars[i] >= '0'))
            dp[i] += dp[i-2];
    }
    return dp[s.length()];
}