温州建网站公司哪家好,cad如何做图纸模板下载网站,本地wordpress安装教程,佛山设计论坛[动态规划] (四) LeetCode 91.解码方法
91. 解码方法 题目解析
(1) 对字母A - Z进行编码1-26
(2)11106可以解码为1-1-10-6或者11-10-6, 但是11-1-06不能解码
(3) 0n不能解码
(4) 字符串非空#xff0c;返回解码方法的总数
解题思路
状态表示
dp[i]#xff1a;以i为结…[动态规划] (四) 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();vectorint 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){//情况1if(s[i] ! 0) dp[i] dp[i-1];//情况2sum (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]初始化为1dp[0]为我们虚构出来的一位因为我们想要使i2dp[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();vectorint dp(n1);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];}
};
