[动态规划] (四) LeetCode 91.解码方法
91. 解码方法
题目解析
(1) 对字母A - Z进行编码1-26
(2)11106可以解码为1-1-10-6或者11-10-6, 但是11-1-06不能解码
(3) 0n不能解码
(4) 字符串非空，返回解码方法的总数
解题思路
状态表示
dp[i]：以i为结尾，的解码方法
状态转移方程
1.单独解码
- dp[i]与dp[i-1]分别解码：s[i]解码成功，即加上dp[i-1]；解码失败，则这种方法以及之前的解码方法dp[i-1]是错误的，方法数0
2.组合解码
- dp[i]与dp[i-1]组合：s[i-1] * 10 + s[i]，解码成功，即加上dp[i-2]；解码失败，则到dp[i-2]的方法是错误的，方法数0
初始化和填表顺序
- 初始化
我们使用了i-1和i-2的值，所以初始化dp[0]和dp[1]。
dp[0]与s[0]有关
dp[1]与s[1]有关，还与s[0]与s[1]的组合有关
dp[0] = s[0] != '0';
if(dp[1] != '0') dp += dp[0];
if(dp[0] != '0' && dp[1] != '0') dp[1] += dp[0];
int sum = ((dp[0] - '0') * 10 + (dp[1] - '0'));
if(sum >= 10 && sum <= 26) dp[1] += 1;
- 填表顺序
从左往右填表
返回值
返回n-1位置即可，同状态表示
代码实现
class Solution {
public:
int numDecodings(string s) {
//构建dp数组
int n = s.size();
vector<int> dp(n);
//初始化
if(s[0] != '0') dp[0] = 1;//单独解码
if(n == 1) return dp[0];
if(s[0] != '0' && s[1] != '0') dp[1] += dp[0];//单独解码
int sum = (s[0] - '0') * 10 + s[1] - '0';
if(sum >= 10 && sum <= 26) dp[1]++;//组合解码
//填表
for(int i = 2; i < n; i++)
{
//情况1
if(s[i] != '0') dp[i] += dp[i-1];
//情况2
sum = (s[i-1] - '0') * 10 + s[i] - '0';
if(sum >= 10 && sum <= 26) dp[i] += dp[i-2];
}
//返回结果
return dp[n-1];
}
};
总结
细节1：字符串中数字进行±*/需要减一个字符0。
细节2：数据范围，字符串长度为1时直接返回dp[0]
细节3：初始化dp[1]时的代码与填表时的代码高度重合，我们可以进行优化
优化方法
1.将申请的空间扩大一位，将填表的下标向后推一位。
2.dp[0]初始化为1，dp[0]为我们虚构出来的一位；因为我们想要使i=2，dp[i]初始化正确，会访问到dp[i-2]。如果dp[0]为0，在计算组合的情况时，就会少加一次dp[i-2]。
3.因为我们把申请的空间dp，填表下标向后推一位，访问字符串s的下标得前进一位，则循环中s[i]的i都得减1。
4.将填表的下标向后推一位，返回值也得向后推一位，即dp[n]。
优化代码
class Solution {
public:
int numDecodings(string s) {
//优化代码
int n = s.size();
vector<int> dp(n+1);
dp[0] = 1;
dp[1] = s[0] != '0';
if(n == 1) return dp[1];
for(int i = 2; i <= n; i++)
{
if(s[i-1] != '0') dp[i] += dp[i-1];
int sum = ((s[i-2] - '0') * 10) + (s[i-1] - '0');
if(sum >= 10 && sum <= 26) dp[i] += dp[i-2];
}
return dp[n];
}
};
