Decode Ways

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

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

//动态规划，和上台阶那道题很类似。
//取string s的前n个字符，记f(n)为这n个字符的所有可能的decoding ways。
//如果s[n]可以被decode,（s[n]在1~9之间），f(n) = f(n - 1);
//如果s[n - 1]和s[n]组合起来可以被一起decode，且s[n]可以被decode。则f(n) = f(n - 2) + f(n - 1);
//如果s[n - 1]和s[n]组合起来可以被一起decode，但s[n]不能被decode。则f(n) = f(n - 2);
//如果上式都不满足，则返回0
class Solution {
public:
    int numDecodings(string s) {
        size_t len = s.size();
        if(len == 0){
            return 0;
        }
        else if(len == 1){
            if(s[0] == '0'){
                return 0;
            }
            else{
                return 1;
            }
        }
        else if(len == 2){
            if(s[0] == '0' || (s[0] > '2' && s[1] == '0')){
                return 0;
            }
            int value = (s[0] - '0') * 10 + s[1] - '0';
            if(value <= 26 && s[1] != '0'){
                return 2;
            }
            else{
                return 1;
            }
        }
        else{
            int dp[len];
            dp[0] = numDecodings(s.substr(0, 1));
            dp[1] = numDecodings(s.substr(0, 2));
            if(dp[0] == 0 || dp[1] == 0){
                return 0;
            }
            for(int i = 2; i < len; i++){
                int value = s[i] - '0';
                if(value <= 9 && value >= 1){
                    dp[i] = dp[i - 1];
                    int value2 = (s[i - 1] - '0') * 10 + s[i] - '0';
                    if(value2 <= 26 && s[i - 1] != '0'){
                        //2 digits decode available
                        dp[i] += dp[i - 2];
                    }
                }
                else{
                    //digit == 0
                    int value2 = (s[i - 1] - '0') * 10 + s[i] - '0';
                    if(value2 <= 26 && s[i - 1] != '0'){
                        //2 digits decode available
                        dp[i] = dp[i - 2];
                    }
                    else{
                        return 0;
                    }
                }
                
            }
            return dp[len - 1];
        }
        
    }
};