dp

f[i][0]表示第s[i]必须和s[i-1]组合，f[i][1]表示s[i]只能单独存在
闫氏dp大法还是秒啊@yxc

class Solution {
public:
    int numDecodings(string s) {
        if (s == "") return 0;
        vector<vector<int>> f(s.size(), vector<int>(2, 0));
        f[0][0] = 0;
        if (s[0] == '0') f[0][1] = 0;
        else f[0][1] = 1;
        for (int i = 1; i < s.size(); i++) {
            if (s[i] == '0') f[i][1] = 0;
            else f[i][1] = f[i - 1][1] + f[i - 1][0];

            int tem = stoi(s.substr(i - 1, 2));
            if (tem >= 10 && tem <= 26) f[i][0] = f[i - 1][1];
            else f[i][0] = 0;
        }
        return f[s.size() - 1][0] + f[s.size() - 1][1];
    }

};