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问题，首先定义一个数组，dp[i]为到第i个字符所能组成的所有编码方式的个数。那么对于dp[i+1]来说，肯定至少和dp[i]一样多，如果第i个字符和i+1个字可以合成一个字符，那么dp[i+1] += dp[i-1]。不过这里需要注意的是违规字符。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int Decode_num(string& str)
{
vector<int> vec(str.size(),0);
if(str.size() <2)
return 1;
vec[0] =1;
if(str[0]=='1' || str[1]<='6')
vec[1] =2;
int i;
int tmp;
for(i=2;i<str.size();i++)
{
if(str[i] != '0') //注意这里需要判断字符串是否为违法字符串
vec[i] = vec[i-1];
tmp = str[i-1]-'0';
tmp = tmp*10 + str[i]-'0';
if(str[i-1]!='0' && tmp <=26) //需要注意判断是够为非法字符串
vec[i] += vec[i-2];
}
return vec[str.size()-1];
}
int main()
{
string str("1231725251414392431271");
//string str("1235533426");
//string str("1224");
cout<<Decode_num(str)<<endl;
cout<<numDecodings(str)<<endl;
return 0;
} 原文：http://blog.csdn.net/yusiguyuan/article/details/44628439