问题描述：
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.
示例：
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
问题分析：
根据题意可知，这是一道动态规划题。dp是状态转移数组，对于s[i - 1] 和 s[i]的不同取值，dp的对应转换过程也不相同。
过程详见代码：
class Solution {
public:
int numDecodings(string s) {
int len = s.length();
if (!len || s[0] == '0') return 0;
vector<int> dp(len + 1, 0);
dp[1] = 1;
dp[0] = 1;
for (int i = 1; i < len; i++)
{
int t = (s[i - 1] - '0') * 10 + s[i] - '0';
if(!t || t > 26 && t % 10 == 0) return 0;
else if(t < 10 || t > 26) dp[i + 1] = dp[i];
else if(t == 10 || t == 20) dp[i + 1] = dp[i - 1];
else dp[i + 1] = dp[i] + dp[i - 1];
}
return dp[len];
}
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
