【DP】【String】Decode Ways

2014-07-23

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.

###思路 DP入门题，比较像stairs

###代码

int numDecodings(string s) {
    int n = s.length();
    vector<int> ways(n, -1);
    return waysEnding(s,  ways, n-1);
}
int waysEnding(string &s, vector<int>& ways, int n){
    if(n < 0) return 0;//处理“”
    if(ways[n] != -1) return ways[n]; //返回备忘录的值
    
    int nway = 0;
    char c = s[n];
    if(c <= '9' && c >= '1'){
        if(n > 0)
            nway += waysEnding(s,ways,n-1);
        else
            nway += 1;
    }
    if(n < 1) return nway;//防止下面n-2出错
    
    int i = stoi(s.substr(n-1, 2));
    if(i <= 26 && i >= 10){
        if(n > 1)
            nway += waysEnding(s,ways,n-2);
        else
            nway += 1;
    }
    ways[n]= nway;//别忘了给备忘录设值，不然会TLE
    return nway;
}

转载请注明出处：【DP】【String】Decode Ways

【DP】【String】Decode Ways

Tech

Life