博文中会简要介绍Leetcode P0091题目分析及解题思路。
“Decode Ways”是一道比较简单的动态规划题，需要考虑的最优子结构比较明显，递推表达式相对比较直接。
A message containing letters from A-Z is being encoded to numbers using the following mapping:
‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 Given a non-empty string containing only digits, > determine the total number of ways to decode it.
具体的递推表达式如下：
令dp[i]等于以s[i-1]为结尾的前缀字符串可以形成的所有可行的编码个数；
dp[0] = 1;
即初始化dp数组
dp[i] += dp[i-2], if i > 1 && s[i-2] != '0' && int(s[i-2:i]) <= 26
如果以s[i-1]为结尾的前缀字符串至少有两个字符，那么若s[i-2]不是'0'，且s[i-2:i]组成的两位数小于等于26，则说明s[i-2:i]可以被编码成一个字符，所以dp[i]要加上所有去掉这两个字符后的前缀字符串的可行编码个数
dp[i] += dp[i-1], if s[i-1] != '0'
无论是否满足上一个条件，若s[i-1]非'0'则dp[i]要加上去掉s[i-1]以后的前缀字符串的所有可行编码数
以下是Java的题解代码实现。
class Solution {
public int numDecodings(String s) {
int len = s.length();
int[] dp = new int[len+1];
dp[0] = 1;
// DP
for (int i1=1; i1<=len; ++i1) {
if (i1 > 1 && s.charAt(i1-2) != '0') {
int code = Integer.parseInt(s.substring(i1-2, i1));
if (code <= 26)
dp[i1] += dp[i1-2];
}
if (s.charAt(i1-1) != '0')
dp[i1] += dp[i1-1];
}
return dp[len];
}
}
以下是C++的题解代码实现。
class Solution {
public:
int numDecodings(string s) {
int len = s.length();
int *dp = new int[len+1];
dp[0] = 1;
// DP
for (int i1=1; i1<=len; ++i1) {
dp[i1] = 0;
if (i1 > 1 && s[i1-2] != '0') {
// C++11标准出现之前
// int code;
// stringstream ss;
// ss << s.substr(i1-2, 2);
// ss >> code;
// C++11标准出现之后
// int code = stoi(s.substr(i1-2,2));
int code = (s[i1-2]-'0')*10+(s[i1-1]-'0');
if (code <= 26)
dp[i1] += dp[i1-2];
}
if (s[i1-1] != '0')
dp[i1] += dp[i1-1];
}
return dp[len];
}
};