class Solution {
public:

    int numDecodings(string s) {
        if(s[0] == '0') return 0;

        int n = s.size();
        vector<vector<int>> f(n + 1 , vector<int>(2 , 0));
    /*
    因为每个字符可以做为单独数字出现，也可以跟另一个数字组合出现 因此将状态划分为两种，
    f[i][0]表示到第i个字符串，且第i个字符做为单独数字出现的方案数；
    f[i][1]表示到第i个字符串，且第i个字符与前一个数组合的方案数。
    */
        f[1][0] = 1;//第1个数无法与前一个数组合
        s = " " + s;
        for(int i = 2 ; i <= n ; i++)
        {
            if(s[i] != '0') f[i][0] = f[i - 1][0] + f[i - 1][1];
            //若当前的数非零，则可以单独出现
            if(s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) f[i][1] = f[i - 1][0];
    /*
    如果当前的数和前一个数符合构造为合法两位数的规则，则当前这个数可以和前一个数一起组合出现，
    其实f[i][1]应该等于f[i-2][0]+f[i-2][1]，但是因为f[i-1][0]=f[i-2][0]+f[i-2][1]，所以可以直接f[i][1] = f[i - 1][0]，
    并且这里不会出现f[i-1][0]未从f[i-2][0]+f[i-2][1]转移而来的情况，因为两个状态转移的条件都是s[i-1]不为零。
    */
        }

        return f[n][0] + f[n][1];
    }
};

也可以优化为一维，只是状态转移的时候要注意一下

class Solution {
public:

    int numDecodings(string s) {
        if(s[0] == '0') return 0;

        int n = s.size();
        vector<int> f(n + 1 ,  0); 

        f[1] = 1;
        s = " " + s;
        for(int i = 2 ; i <= n ; i++)
        {
            if(s[i] != '0') f[i] = f[i - 1]; 
            if(s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) f[i] += (i == 2 ? 1 : f[i - 2]); 
        }

        return f[n];
    }
};