原题：
给定一串数字，求出有多少种编码方式。看完这道题目，第一反应想到的是使用DFS。一个字母最多编码成一个两位数，因此每次遍历的时候要么取一个数字，要么两个数字，每次遍历的时候判断数字是否合法，若能遍历到最后一个数字则编码成功。比如说，我以"101"为例：第一次取"1"，然后判断"1"有没有对应的字母，若存在，则截掉第一个数字，剩下"01"，继续进行递归，否则直接返回；或者判断"10"有没有对应的字母，若存在，则截掉前面两个数字，剩下"1"，继续进行递归，否则直接返回。若最后只剩下一个空字符串，则解码成功。大致就是对一棵二叉树进行遍历一遍。这样的解法在少量数据的情况下还能用。代码大概是这样，在leetcode提交后，毫无悬念得提示超时。
class Solution {
public:
int numDecodings(string s) {
if (s.empty()) {
return 0;
}
int result = 0;
dfs(s, &result);
return result;
}
private:
bool isValidLetter(string str) {
if (str[0] == '0') {
return false;
}
int num;
if (str.size() == 1) {
num = str[0] - '0';
} else {
num = (str[0] - '0') * 10 + (str[1] - '0');
}
return num >= 1 && num <= 26;
}
void dfs(string str, int *result) {
if (str.size() >= 1) {
if (isValidLetter(str.substr(0, 1))) {
dfs(str.substr(1), result);
} else {
return;
}
}
if (str.size() >= 2) {
if (isValidLetter(str.substr(0, 2))) {
dfs(str.substr(2), result);
} else {
return;
}
}
if (str.size() == 0) {
(*result)++;
}
}
};
这道题可以用动态规划来做，dp[i]表示前i个(包括i)数字有多少种解码方式。当i=0时，dp[0] = 0; i = 1呢，dp[1]就等于1吗？未必，可能第一个数字为0，那就无法解码出对应的字母，因此还需要视情况而定。当i=n呢，第n个数字可能单独作为一个字母，也可能与它前一个数字组合成一个字母。因此，我们初步得到状态转移方程：
(1) dp[0] = 0
(2) dp[1] = 1, if str[1] is valid
dp[1] = 0, if str[1] is not valid
(3) dp[n] = dp[n - 1] + dp[n - 2]
第三个方程咋看起来好像没有问题，但是第n个数字就一定能保证可以解码成一个合法的字母？同样，第n个数字与它前一个数字的组合就一定保证解码成一个合法的字母？在上述状态转义方程中，我们没有对它进行判断。经过分析后，第三个方程看起来应该是这样的：
dp[n] = 0
if str[n] is valid
dp[n] += dp[n - 1]
if str[n - 1] combine str[n] is valid
dp[n] += dp[n - 2]
看起来完美了，但上面的代码还有个小问题。当n = 2时，若第2个字母与第一个字母的组合合法，则dp[2] += dp[0]，但是dp[0]我们一开始已经给它赋值为0。因此当n = 2时，即使合法，也相当于没有进行累加。所以，这里要稍加判断，修改后的代码如下：
dp[n] = 0
if str[n] is valid
dp[n] += dp[n - 1]
if str[n - 1] combine str[n] is valid
dp[n] += (i - 2 == 0) ? 1 : dp[n - 2]
正确得写出状态转义方程后，实现代码应该不难：
class Solution {
public:
int numDecodings(string s) {
int dp[s.size() + 1];
//将数组初始化为0
memset(dp, 0, sizeof(int) * (s.size() + 1));
//判断第一个数字是否合法，若不合法，直接返回0
if (s.size() >= 1) {
if (isValid(s[0])) {
dp[1] = 1;
} else {
return 0;
}
}
for (int i = 1; i < s.size(); i++) {
if (isValid(s[i])) {
dp[i + 1] += dp[i];
}
if (isValid(s[i - 1], s[i])) {
dp[i + 1] += ((i-1)==0?1:dp[i - 1]);
}
}
return dp[s.size()];
}
private:
bool isValid(char c1, char c2) {
if (c1 == '0') {
return false;
}
int num = (c1 - '0') * 10 + (c2 - '0');
return num >= 1 && num <= 26;
}
bool isValid(char c) {
int num = c - '0';
return num >= 1 && num <= 26;
}
};
