给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof

方法1：自己想的笨方法：空间换时间

/*
思路：建立两个数组：vec1用于存储已成功翻译的字符串的最后一个字符,vec2用于临时做各种处理。
扫描输入数字,进入vec2中，从vec1选出每个数字与输入数字组合，若在10-25之间，进入vec2,同时vec的数字还要作为单独字符进入vec2,代码里还有些小细节。

首先我们来通过一个例子理解一下这里「翻译」的过程：我们来尝试翻译「1402」。
分成两种情况：
首先我们可以把每一位单独翻译，即 [1, 4, 0, 2][1,4,0,2]，翻译的结果是 beac
然后我们考虑组合某些连续的两位：
1. [14, 0, 2][14,0,2]，翻译的结果是 oac。
2. [1, 40, 2][1,40,2]，这种情况是不合法的，因为 4040 不能翻译成任何字母。
3. [1, 4, 02][1,4,02]，这种情况也是不合法的，含有前导零的两位数不在题目规定的翻译规则中，那么 [14, 02][14,02] 显然也是不合法的。

归纳出翻译的规则，字符串的第i 位置：
1. 可以单独作为一位来翻译
2. 如果第i - 1位和第i位组成的数字在 10到 25之间，可以把这两位连起来翻译。
*/
int translateIntToChar(int number)
{
    if (number <= 0)
        return 0;
    if (number >= 0 && number <= 9)
        return 1;

    string strNumber = to_string(number);
    vector<int> vec1;//存储第i位数字为止能存储的所有数字翻译方法
    vector<int> vec2;//用于临时交换

    //每次遍历到新数时，先让单个数进vec2，然后依次从vec1中取数字与新数匹配，看能否组合表示一个数，若能，进入vec2，直到vec1中数完全取出。最后ve2中数转到vec1中
    for (int i = 0; i < strNumber.size(); ++i)
    {
        int newNum = strNumber[i] - '0';
        vec2.push_back(newNum);
        vector<int>::iterator it = vec1.begin();
        while (it!=vec1.end())
        {
            int oldNum = *it;
            int num = oldNum * 10 + newNum;
            if (num >= 0 && num <= 25&&!(oldNum==0&&newNum>=0))
            {
                vec2.push_back(num);
            }
            if (it < vec1.end() - 1)
            {
                vec2.push_back(newNum);
            }
            ++it;
        }
        vec1=vec2;

        cout << "i：" << i << endl;
        for (int j = 0; j < vec1.size(); ++j)
        {
            cout << vec1[j] << "  ";
        }
        cout << endl;

        vec2.clear();
    }
    return vec1.size();
}

方法2：动态规划

这个思路看上面的力扣链接吧
代码：

class Solution {
public:
    int translateNum(int number) {
        if (number < 0)
            return 0;
        if (number >= 0 && number <= 9)
            return 1;

        string str = to_string(number);
        //x初始化为下标-1对应的字符串数量，也即后来的i-2。y初始化为下标0对应的字符串数量，也即后来的i-1
        int x = 1, y = 1;
        int z = 0;
        //数组下标从1开始
        for (int i = 1; i < str.size(); ++i)
        {
            //数组i下标的值，
            int p = str[i] - '0';
            //若i与i-1能成对
            int sum = p + 10*(str[i - 1]-'0');
            if (sum >= 10 && sum <= 25)
            {
                z = y + x;
            }
            else
            {
                z = y;
            }
            //cout << "x=" << x << "    y=" << y << "   z=" << z << endl;
            x = y; 
            y = z;
        }
        return z;
    }
};