题目描述

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

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

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

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

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

数据范围

输入数字位数 [1,101]。

样例

输入："12258"
输出：5

方法一：动态规划 O(n)

状态表示：f[i] 表示将前 i 位数字翻译成字符串的方案数。

状态计算：

f[i] = f[i-1] ，当前位的数字只算一位是一定能构成合法方案的。

只有当当前位的数字和它前面的那一位能构成 10 ~ 25 之间的数字时，f[i] += f[i-2] 。

可以发现这个思路和递推的思想很类似，由两个方向可以递推过来，我们举一个例子，假如当前已经遍历到 142 ，第三位是 2 ，它可以由前面一位的方案转移过来即 f[i] = f[i-1] 。但是发现 42 并不在 10 ~ 25 的范围内，所以不能转换成字母，所以就不用从前两位的方案转移过来。

class Solution {
public:
    int getTranslationCount(string s) {
        int n = s.size();
        vector<int> f(n + 1); 
        f[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            f[i] = f[i - 1];
            int t = (i >= 2) * (s[i - 2] - '0') * 10 + s[i - 1] - '0';
            if (t >= 10 && t <= 25)    f[i] += f[i - 2];
        }
        return f[n];
    }
};

欢迎大家在评论区交流~