题解 | #把数字翻译成字符串#

这题有点像跳箱子（一次跳一格或者两格）

如果按照跳箱子的做法，dp[n] = dp[n-2] + dp[n-1],从后往前递归，会超时（递归时间和空间都会超）；

那么可以用从前往后的动态规划：

从前往后遍历，分类讨论当前元素i：

1. 如果i == 0，那么前一个字符必须为1或者2，此时dp[i] = dp[i - 2],否则无法译码，直接返回0；
2. 如果i != 0，考虑i-1:

   1. 如果i - 1 == 0，那么当前i只能单独译码，则dp[i] = dp[i - 1]；

   2. 如果i - 1 != 0,那么看string(i - 1, i)是否在10~26之间，在的话dp[i] = dp[i - 2] + dp[i - 1], 否则dp[i] = dp[i - 1]

class Solution {
public:
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        // write code here
        if(!nums.size() || nums[0] == '0')
            return 0;
        vector<int> count;
        count.push_back(1);//占位
        count.push_back(1);
        for(int i = 1; i < nums.size(); i ++){
            if(nums[i] > '0'){
                if(nums[i - 1] == '0')
                    count.push_back(count[i]);
                else if(nums.substr(i-1,2) <= "26")
                    count.push_back(count[i - 1] + count[i]);
                else 
                    count.push_back(count[i]);
            }
            else{
                if(nums[i - 1] == '1' || nums[i - 1] == '2')
                    count.push_back(count[i - 1]);
                else
                    return 0;
            }
        }
        return count.back();
    }
};