DP $O(n)$

solution in comment

C++ 代码

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> f(n + 1, 0);
        f[0] = 1;
        for(int i = 1; i <= n; i++) {
            if(s[i-1] - '0' > 0) f[i] += f[i-1];
            if(i - 2 >= 0) {
                int t = 10 * (s[i-2] - '0') + (s[i-1] - '0');
                if(t >= 10 && t <= 26) f[i] += f[i-2];
            }
            // cout << i << ':' << f[i] << endl;
        }
        return f[n];
    }
};

// f[i]: s[1..i]解码方式的集合
// 属性: s[1..i]解码方式的数量
// 集合划分:
//      每个数字，可能单独编码，也可能一起编码
//      若s[i]单独编码, s[i] > 0: f[i-1]
//      若s[i]与s[i-1]一起编码, s[i-1] * 10 + s[i] in [10, 26]: f[i-2]