题目描述

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

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

思路：

动态规划，和跳台阶很像，每次只能跳一级或者两级台阶，总共多少种可能
这个是每两位数(10-25范围内)可以合并翻译，可以分开翻译，超出范围的只能分开翻译

f(i)=f(i−1)+f(i−2)   [i−1≥0,10≤x≤25]
f(i)=f(i−1)+f(i−2)   [else]

递归吧，从后往前遍历字符串，最底层的len为0或者1的情况，都只有一种翻译结果，都返回1

class Solution {
public:
    int translateNum(int num) {
        return Count(to_string(num));
    }
    int Count(string s) {
        int len=s.size();
        if(len==0||len==1) return 1;//len=0时返回1，因为len=2时，有两种可能 len(2)=len(1)+len(0)
        if("10"<=s.substr(len-2,2)&&s.substr(len-2,2)<="25")
        //这个范围的字符可以分成两个数字，可以合成一个数字
            return Count(s.substr(0,len-2))+Count(s.substr(0,len-1));
        else
            return Count(s.substr(0,len-1));
    }
};