46.把数字翻译成字符串（中等）

考点：本题考查递归和时间效率

题目描述：

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

思路：从最小的子问题开始自下而上解决问题

定义函数f(i)表示从第i位数字开始的不同翻译的数目，那么f(i)=f(i+1)+g(i,i+1)×f(i+2)。当第i位和第i+1位两位数字拼接起来的数字在10-25的范围内，函数g(i,i+1)的值为1；否则为0。
递归是从最大的问题开始自上而下解决问题，用递归的思路来分析这个问题，存在重复的子问题。所以可以从最小的子问题开始自下而上解决问题，这样就可以消除重复的子问题。也就是，从数字的末尾开始，然后从右到左翻译并计算不同翻译的数目。

class Solution {
    public int translateNum(int num) {
        if(num<0)
            return 0;
        int count = 0;
        String str = String.valueOf(num);
        int len = str.length();
        int[] counts = new int[len];
        for(int i = len - 1;i>=0;i--){
            // int count = 0;
            if(i<len - 1)
                count = counts[i+1];
            else
                count = 1;
            if(i<len-1){
                int a = str.charAt(i)-'0';
                int b = str.charAt(i+1)-'0';
                int converted = a*10+b;
                if(converted>=10&&converted<=25){
                    if(i<len-2)
                        count+=counts[i+2];
                    else
                        count+=1;
                }
            }
            counts[i]=count;
        }
         return count;
    }

    
}