面试题46(剑指offer)--把数字翻译成字符串

题目：

给定一个数字，按照如下规则翻译成字符串：0翻译成“a”，1翻译成“b”…25翻译成“z”。一个数字有多种翻译可能，例如12258一共有5种，分别是bccfi，bwfi，bczi，mcfi，mzi。实现一个函数，用来计算一个数字有多少种不同的翻译方法。

思路：

动态规划，dp[i]表示从个位到第i位，一共有多少种表达方式，以12345为例，当第i位和i+1位的值大于25时，比如34，因为3和4不能用一个字母表示所以345表示方式数与45的表示数一样；如果小于25，则dp[i]=dp[i+1]+dp[i+2]，也与i+2位有关，比如1这一位，可以有1+2345的表示数和12+345的表示数的和。

代码：

    private static int num(int number){
        String num=number+"";
        char[] arr=num.toCharArray();
        int len=arr.length;
        if (len<2){
            return 1;
        }
        int[] dp=new int[len];
        dp[len-1]=1;
        if ((int)arr[len-2]-48+(int)arr[len-1]-48<=25){
            dp[len-2]=2;
        }else {
            dp[len-2]=1;
        }
        for (int i = len-3; i >=0 ; i--) {
            int temp=(arr[i]-48)*10+(arr[i+1]-48);
            if (temp<=25){
                dp[i]=dp[i+1]+dp[i+2];
            }else {
                dp[i]=dp[i+1];
            }
        }
        return dp[0];
    }