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

class Solution {
  public:
    /**
        数字范围是1到26，建立同样大小的vector, dp[i] = dp[i-1] + dp[i-2](如果可以这个和前一个能组成一个)；
        遇到0，自己不能成组，看前面，若前面不是1和2则不能编译；
		动态规划，dp[i]表示以这个结尾有多少种可能，根据前一个字符的情况，更新当前
     */
    int solve(string nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) {
            if (nums[0] == '0')return 0;
            else return 1;
        }

        vector<int> dp( nums.size() );

        if (nums[1] == '0' ) {
            if (nums[0] != '1' && nums[0] != '2') {
                return 0;
            } else {
                dp[0]=1;
                dp[1]=1;
            }
        } else {
            if (nums[0] == '0')return 0;
            else if ( stoi(nums.substr(0, 2)) > 26 ) {
                dp[0] = 1;
                dp[1] = 1;
            } else {
                dp[1] = 2;
                dp[0] = 1;
            }
        }


        for (int i = 2; i < nums.size(); i++) {
            if (nums[i] == '0' ) {
                if (nums[i - 1] != '1' && nums[i - 1] != '2') {
                    return 0;
                } else {
                    dp[i] = dp[i - 2];
                }
            } else {
                if (nums[i - 1] == '0')dp[i] = dp[i - 1];
                else if ( stoi(nums.substr(i - 1, 2)) > 26 ) {
                    dp[i] = dp[i - 1];
                } else {
                    dp[i] = dp[i - 1] + dp[i - 2];
                }
            }
        }

        return dp.back();
    }
};