把数字翻译成字符串

题目: 给定一个数字，我们按照如下规则把它翻译为字符串：0翻译成”a”，1翻译成”b”，……，11翻译成”l”，……，25翻译成”z”。一个数字可能有多个翻译。一个数字有多少种不同的翻译方法。

此题是一个递归问题。递归式为:f(i)=f(i-1)+g(i)*f(i-2)。当最后两个数字在10到25之间g(i)才等于1。由于有重叠子问题，可以考虑用动态规划，自底向上求解。此题与青蛙跳台阶类似，难点在于判断g(i)哪时候等于1.

参考代码

/**
 * 把数字翻译成字符串,共有多少种翻译方案
 */
public class NumInString {
    public int getTranslationCount(int number){
        if (number<0)
            return 0;
        else
            return getTranslationCount(Integer.toString(number));
    }
    public int getTranslationCount(String number){
        char[] numberarray=number.toCharArray();
        int[] counts=new int[number.length()];//储存第i个数时,共有多少种翻译方案
        for (int i = 0; i <number.length() ; i++) {
            if (i==0)
                counts[i]=1;
            if (i==1)
            {
                counts[i]=1;
                int temp=numberarray[i]-'0'+(numberarray[i-1]-'0')*10;
                // 前两位也可以用一个字符表示
                if (temp>=10&&temp<=26){
                    counts[i]+=1;
                }
            }

                if (i>1){
                    counts[i]=counts[i-1];
                    int temp=numberarray[i]-'0'+(numberarray[i-1]-'0')*10;
                    // 前两位也可以用一个字符表示
                    if (temp>=10&&temp<=25){
                        counts[i]+=counts[i-2];
                    }
                }
            }
        return counts[number.length()-1];

    }
    public static void main(String[] args){
        int number=-1;
        NumInString numInString=new NumInString();
        System.out.println(numInString.getTranslationCount(number));
    }
}