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

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

一个数字可能有多个翻译。

例如 12258 有 5 种不同的翻译，它们分别是 bccfi、bwfi、bczi、mcfi 和 mzi。

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

blablabla

样例

输入："12258"

输出：5

算法1

动态规划

算法思想

看到多少种方案，那么第一反应就是动态规划，只要是计数问题，那一般就是动态规划了
第一：状态表示 ，f(i) 表示前i个数字一共有多少种不同的翻译方式.
第二：状态计算 ，第i个数字的翻译方式有两部分组成，如果第 i 位数字单独作为一个数字，那么就有前i - 1 个数字的表示方式 ，也便是f(i - 1)，第二部分是第i个数字与第i - 1 个数字能够组合成一个数字来表示，
也就是两个数字应该是在10 - 25 之间的数，包括边界，根据题意，00-09是不能翻译成一个数字，所以，当这种情况发生时候，就加上f(n - 2)；

编程技巧

由于需要记录前i - 1 和前 i - 2 的状态，为了避免麻烦，设置一个状态数组进行存储之前计算的状态，当然也可以用两个变量来存储

时间复杂度

O(n)

参考文献

Java 代码

class Solution {
    public int getTranslationCount(String s) {
        char[] a = s.toCharArray();
        int len = a.length;
        int[] d = new int[len];
        d[0] = 1;
        for(int i = 1; i <len; i ++)
        {
            int x = a[i] - '0';
            int y = a[i - 1] - '0';
            int z = y * 10 + x;
            if(z >= 10 && z <= 25 )
            {
                if(i == 1) d[i] = 2;
                else d[i] = d[i - 1] + d[i - 2];
            }
            else d[i] = d[i - 1];
        }
        return d[len - 1];
    }
}