//这里有递归的做法和动态规划的做法参考
/*
class Solution {
public:
    //表示从a的index位置开始之后有多少种译码结果
    int f(string a,int index){
        if(index==a.length()) return 1;
        int p1=0;
        //两格走
        if(index+1<a.length()&&(a[index]=='1'||(a[index]=='2'&&a[index+1]<='6'))){
            p1=f(a,index+2);
        }
        int p2=0;
        if(a[index]!='0')
            p2=f(a,index+1);
        return p1+p2;
    }
    int solve(string nums) {
        return f(nums,0);
    }
};//递归
*/
class Solution {
  public:
    int solve(string nums) {
        int n = nums.size();
        vector<int> dp(n + 1, 0);
        dp[n] = 1;
        for (int i = n - 1; i >= 0; i--) {
            int p1 = 0;
            if (i + 1 < n && (nums[i] == '1' || (nums[i] == '2' && nums[i + 1] <= '6'))) {
                p1 = dp[i + 2];
            }
            int p2 = 0;
            if (nums[i] != '0') {
                p2 = dp[i + 1];
            }
            dp[i] = p1 + p2;
        }
        return dp[0];
    }
};//动态规划