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

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        //1.申请dp数组,第i位数字有dp[i]种组合方法
        if(nums.size() == 0)return 0;
        if(nums == "10" || nums == "20")return 1;

        vector<int> dp;
        dp.resize(nums.size() + 1,0);

        //如果0前面不是1或者是2，无法译码
        for(int i = 0;i < nums.size();i++){
            if(nums[i] == '0'){
                if(i == 0)return 0;
                if(nums[i - 1] != '1' && nums[i - 1] != '2'){
                    return 0;
                }
            }
        }



        //2.初始化dp数组
        dp[0] = 1;
        dp[1] = nums[0] - '0' > 0 && nums[0] - '0' <= 9 ? 1 : 0;

        //3.递推公式
        for( int i = 2; i <= nums.size() ; i++ ){
            //判断是否能组合
            int num = stoi(nums.substr( i - 2, 2).c_str());
            if(num == 10 || num == 20){
                dp[i] = dp[i - 2];
            }
            else if(num >= 10 && num <= 26){

                dp[i] = dp[i - 2] + dp[i - 1];
            }
            else if(nums[i - 1] >= '1' && nums[i - 1] <= '9'){
                dp[i] = dp[i - 1];
            }
        }

        return dp[nums.size()];
    }
};

题解：使用动态规划。动规五部曲：1）确定dp数组含义：第i位数字有dp[i]种组合方法；
2）递推公式：对于第i位字符组合的情况，首先要看它是否能和前一个字符进行结合，如果可以结合成10或20，那么第i个字符一定要和第i - 1个字符进行结合，那么第i个字符的组合情况也就是dp[i - 2]；如果组合成大于10并小于26的数，那么就即可以与前一个字符进行结合进行译码，也可以自己单独译码一共两种情况，所以dp[i] = dp[i - 1] + dp[i - 2];如果结合不了，那么就看是否在1-9之间，在的话就可以单独编码，所以dp[i] = dp[i - 1]。
3)初始化：dp[0] = 1 无意义，为了方便第2位进行计算，dp[1] = nums[i] >= ‘1’ && nums[i] <= ‘9’ ? 1 : 0;   4）遍历顺序：从头到尾。
该题解的时间复杂度是ｏ（ｎ），空间复杂度是Ｏ（ｎ）。