题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：

0翻译成”a”，1翻译成”b”，……，11翻译成”l”，……，25翻译成”z”。

一个数字可能有多个翻译。例如12258有5种不同的翻译，它们分别是”bccfi”、”bwfi”、”bczi”、”mcfi”和”mzi”。

请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

样例

输入："12258"

输出：5

算法1

借第一位题解的思路。
以dp[i]表示从字符串i位开始到末尾，最大的翻译次数。

dp[i] = dp[i+1] // default, 比如都是67876878，这种只有1种解码方式，不会增加 = dp[i+1] + dp[i+2] // when s[i]==‘1’||(s[i]==‘2’&&s[i+1]<‘6’) 这种情况的出现会使解码次数增加
举个例子12xxxxxx;将1作为单独的一个数看，解码方法和2xxxxxx相同
；将12作为一个整体看，解码方法数量和xxxxxx相同。
最终的数量是二者之和。
上面的算法是正确的，但是，建立的这个dp数组，如果数字只有一位，那dp[0]=1，没问题，所以一开始给定dp[n-1]=1;
当输入的值在26之内的时候，当前的dp[i]要加上dp[i+2],所以，一开始的初始值dp[n]也应该给定为1，避免从右边开始的两位小于26，如果没有给定dp[n]=1，将会减少一次结果

JAVA 代码

class Solution {
    public int getTranslationCount(String s) {
        char[] ch = s.toCharArray();
        int n = s.length();
        if(n==0)return 0;
        if(n==1)return 1;

        int[] dp = new int[n+1];
        dp[n-1] = 1;
        dp[n]=1;
        for(int i =n -2; i>=0;i--){
            dp[i]=dp[i+1];
            if(ch[i]=='1'||(ch[i]=='2'&&ch[i+1]<'6'))
            dp[i]+=dp[i+2];
        }
        return dp[0];
    }
}