剑指offer 47- 把数字翻译成字符串

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

翻译成 ，翻译成 翻译成翻译成

一个数字可能有多个翻译

例如 12258
有 5种不同的翻译，它们分别是 bccfi、bwfi、bczi、mcfi 和 mzi。
请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

样例

输入："12258"

输出：5

分析：dp
加强版的爬楼梯问题
（1）状态表示：f（i）前i位数字有多少种表示方式
（2）状态如何计算
第i位翻译成单独的字母：f（i） = f（i-1）
第i位和i-1位合在一起翻译成字母：f（i） = f（i-2）
（3）边界问题：f（0）=1
时间复杂度：

class Solution {
public:
    //加强版的爬楼梯问题
    int getTranslationCount(string s) {
        int n = s.size();
        vector<int> f(n+1);//因为从0开始，这里要加上1
        f[0]=1;
        for(int i=1;i<=n;i++) {
            f[i] = f[i-1];
            int t = (s[i-2] - '0')*10 + (s[i-1] - '0');
            if(t>=10 && t<=25) f[i] += f[i-2];
        }
        return f[n];
    }
};