动态规划之解码方法
91. 解码方法解法1解法2
91. 解码方法
91. 解码方法
解法1
状态表示（这是最重要的）：dp[i]表示以第i个字符为结尾，解码方法的总数。 状态转移方程（最难的）：根据最近的一步来划分问题，从右向左思考，我们需要考虑s[i]和s[i-1]是单独为一个字符形成两个数字，还是合并为一个字符形成为一个数字。 如果s[i]和s[i-1]是单独为一个字符形成两个数字，那么dp[i]的值就是dp[i-1]的值； 如果s[i]和s[i-1]合并为一个字符形成为一个数字，那么dp[i]的值就是dp[i-2]的值。因为s[i]和s[i-1]都形成一个数字了，再dp[i]往前就是就是dp[i-2]了。 因为单独一个0不能解码，所以当s[i]和s[i-1]是单独为一个字符时，若s[i]为’0’，dp[i] = 0; 如果形成的两位数数字不在[10, 26]区间内的话（因为前导0不能编码，所以不是[1, 26]），所以当s[i]和s[i-1]合并为一个字符时，若超出这个范围了，dp[i] = 0; 初始化：因为我们得状态转移方程里面包含dp[i-1]和dp[i-2]，所以我们需要初始化dp[0], dp[1]，以免越界及无法计算。dp[0]就只有一个,我们只需要判断它是不是不为’0’即可，dp[0] = s[0] != '0';。 dp[1]的话有两种情况，单独为两个数1且分开成两个数，单独为一个数需要判断形成的这一个数是否在[10, 26]这个范围里面；分别为两个数只需要判断s[0]和s[1]是不是都不为’0’。 填表顺序：当我们求解当前问题时，需要知道所需较小子问题的解，这就需要我们先求解得到较小子问题的解，这就是填表顺序。我们这道解法是从左向右填表。 返回值：return dp[n-1];
代码实现：
class Solution {
public:
int numDecodings(string s) {
// 创建dp表
int n = s.size();
vector
// 初始化
dp[0] = s[0] != '0';
// 处理边界问题
if(1 == n) return dp[0];
if(s[0] != '0' && s[1] != '0') dp[1] = 1;
int count = (s[0]-'0')*10 + s[1]-'0';
if(count >= 10 && count <= 26) dp[1]++;
// 填表
for(int i = 2; i < n; i++)
{
if(s[i] != '0') dp[i] += dp[i-1];
int count1 = (s[i-1]-'0')*10 + s[i]-'0';
if(count1 >= 10 && count1 <= 26) dp[i] += dp[i-2];
}
// 返回
return dp[n-1];
}
};
解法2
当我们观察解法1中的代码时，我们会发现如下图两个红圈中的代码是类似的，那么是否可以简化代码呢？ 我们可以可以将解法1中的dp数组整体向右移动一个元素的位置， 解题思路和解法1一样，如此一来我们只需要初始化新增加的dp[0]和dp[1]（解法1中dp数组的dp[0]）。 dp[1]的初始化跟解法1一样：dp[1] = s[0] != '0';。 但是dp[0]由于没有对应的字符，我们该如何给它赋值呢？ 按理来说既然没有对应字符，那么我们应该将dp[0]初始化为0。如果这样的话，我们得代码将是这样的：
class Solution {
public:
int numDecodings(string s) {
// 创建dp表
int n = s.size();
vector
// 初始化
dp[0] = 0;
dp[1] = s[0] != '0';
// 填表
for(int i = 2; i <= n; i++)
{
if(s[i-1] != '0') dp[i] += dp[i-1];
int count1 = (s[i-2]-'0')*10 + s[i-1]-'0';
if(count1 >= 10 && count1 <= 26) dp[i] += dp[i-2];
}
// 返回
return dp[n];
}
};
在我们将注意力放在红圈里面，在计算dp[2]时，我们会发现，明明s[0]和s[1]组成的数字已经在[10, 26]这个范围之中了，但是dp[i] += dp[i-2]这个代码不能让dp[i]也就是dp[2]有任何变化，因为dp[i-2]也就是dp[0]被初始化为0了，但是应该使得dp[i]也就是dp[2]加上1的。所以，在我们初始化时，我们要将dp[0]初始化为1。 代码实现：
class Solution {
public:
int numDecodings(string s) {
// 创建dp表
int n = s.size();
vector
// 初始化
dp[0] = 1;
dp[1] = s[0] != '0';
// 填表
for(int i = 2; i <= n; i++)
{
if(s[i-1] != '0') dp[i] += dp[i-1];
int count1 = (s[i-2]-'0')*10 + s[i-1]-'0';
if(count1 >= 10 && count1 <= 26) dp[i] += dp[i-2];
}
// 返回
return dp[n];
}
};
创作不易，你的点赞和关注都是对我莫大的鼓励，再次感谢您的观看
参考阅读
发表评论