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.
有多少种解码可能，这里的‘A‘~‘Z‘已经被转化成数字字符了
class Solution {
public:
int numDecodings(string s) {
if(s.empty())
return 0;
int res[s.size()+1];
res[0]=1;
res[1]=(s[0]=='0'?0:1);
for(int i=2;i<=s.size();i++)
{
if(s[i-1]=='0')
res[i]=0;
else
res[i]=res[i-1]; //一个元素只有一个可能，所以继承前一位的
if(s[i-2]=='1'||(s[i-2]=='2'&&s[i-1]<='6')) //1~26 //两种可能，可能性翻倍
res[i]=res[i]+res[i-2];
}
return res[s.size()];
}
};原文：http://blog.csdn.net/u011391629/article/details/52175729