91. 解码方法

思路:

class Solution {
public:
    //dp方法，dp[i]表示前i个字母的有效解码的个数
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') {
            return 0;
        }
        int dp[s.size() + 1];
        dp[0] = 1;
        for (int i = 1; i < s.size() + 1; i++) {
            if (s[i - 1] == '0') {
                dp[i] = 0;
            } else {
                dp[i] = dp[i - 1];
            }
            if (i > 1 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.size()];
    }
};