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

解法：DP

翻译成什么不重要，这只是限制了数字的范围是0~25
假设从开头到第i个字符，翻译方法一共有f[i]种，那么

• s[i]肯定可以单独翻译，此时f[i] = f[i - 1]
• s[i]如果能够和s[i - 1]合起来翻译，也就是数值在10~25之间，那么f[i] += f[i - 2]

时间复杂度O(n)，空间复杂度O(n)

class Solution {
public:
    int getTranslationCount(string s) {
        int len = s.size();
        int cnt[len];
        cnt[0] = 1;
        for (int i = 1; i < len; i++) {
            cnt[i] = cnt[i - 1];
            if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '5')) {
                if (i >= 2) cnt[i] += cnt[i - 2];
                else cnt[i] += 1;
            }
        }
        return cnt[len - 1];
    }
};