A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

class Solution{
public:
    int numDecodings(string s){
        int n = s.size();
        if(n == 0) return 0;
        vector<int> memo(n+1,-1);
        memo[0] = 1;
        memo[1] = s[0] == '0' ? 0:1;
        for(int i = 2; i <= n; i++){
            if(s[i-1] == '0'){
                if(s[i-2] == '1' || s[i-2] == '2'){
                    memo[i] = memo[i-2];
                }
                else{
                    memo[i] = 0;
                }
            }
            else
            {
                if(s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')){
                    memo[i] = memo[i-1] + memo[i-2];
                }
                else
                {
                    memo[i] = memo[i-1];
                }
            }
        }
    }
};

参考：

1，https://blog.csdn.net/u013250416/article/details/80558542