注意判断数字合格，不要漏掉合格字符或者不合格字符

const int N = 110;

class Solution {
public:

    int dp[N];

    bool isValid(string sub){
        if(sub == "") return true;
        int n = sub.size();
        if(n == 1 && sub[0] != '0') return true;
        if(n == 2 && sub[0] == '1') return true;
        if(n == 2 && sub[0] == '2' && sub[1] < '7') return true;
        return false;
    }
    int numDecodings(string s) {
        if(s[0] == '0') return 0;
        int sum = 0;
        int n = s.size();
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        dp[1] = 1;
        //dp[2] = (isValid(s.substr(0, 2))? 1 : 0) + (isValid(s.substr(1, 1)? 1 : 0);
        for(int i = 2; i <= n; i++){
            if(isValid(s.substr(i-1, 1))){
                dp[i] += dp[i-1];
                //printf("%d = %d\n",i, dp[i]);
            }
            //cout << i << " sub= " << s.substr(i-2, 2) << endl;
            if(isValid(s.substr(i-2, 2))){
                //cout << i << " sub= " << s.substr(i-2, 2) << endl;
                dp[i] += dp[i-2];
                //printf("%d = %d\n",i, dp[i]);
            }
        }
        // printf("dp[4]%d\n", dp[4]);
        // printf("dp[5]%d\n", dp[5]);
        // printf("dp[11]%d\n", dp[11]);
        return dp[n];
    }
};