tCodehttps://leetcode.cn/problems/decode-ways/description/

一、题目解析

题目大意从题目中我们可以知道解码就是在字符串s中由‘1’到‘26’的字符可以转化成字母A到Z在所给的一个字符串中我们有很多种解码方式可以解出不一样的答案。

我们在解码时可以单个单个解码也可以由两个字符组合解码但是需要注意我们单个字符时不可以是0两个字符组合解码时需要大于等于10小于等于26

拿题例子来讲:我们不可以以0开头即不可以是06也不可以是60因为大于26无法解码第二位如果是0那第一位只能是1或2。

二、算法原理

我们在状态标识的时候一般都会创建一个数组dp也就是我们所说的dp表我们要做的就是把每一个状态的值填入这个表内最终这个表内的某一个值可能就是我们要返回的值。

如何确定状态表示

越学越深入动态规划也是熟能生巧在题目中没有明显给出的时候我们就要凭借自己做题的经验来确定所以就需要我们大量的做题。

分析问题的过程中把重复子问题抽象成我们的状态表示这个更难理解一切的基础都是我们先对动态规划算法熟练运用。

我也不懂我们慢慢来。

那我们的这道题得状态表示是什么样的我们根据经验所判断我们可以以某个位置为结尾

2、状态转移方程

我们根据状态表示再结合题目经验去推理转移方程这一步也是我们整个解题过程中最难的一步

在解之前我们需要判断i位置码是否符合我们的解码要求如果不符合那就会解码失败然后之前的一切努力都会白费

我们要清楚我们dp[i]表示我们解码到i位置时的解码方法当解码时如果解码成功就加上dp[i-1]或者dp[i-2]即可因为我们并没有解码完成功代表可以继续解码直到解码完。

3、初始化

我们创建dp表就是为了把他填满我们初始化是为了防止在填表的过程中越界

怎么谈越界

我们不进行初始化那我们在填表时就比如dp[0]在填表时根本没有dp[-1]和dp[-1],这就会导致越界所以我们需要对dp[0]初始化。

在这道题中我们需要对dp[0]、dp[1]初始化但是因为下表映射我们可以在填表时将dp[1]初始化(映射后的dp[1]变成dp[2]),具体注释看我下方代码

下标映射

我们为了在敲代码过程中方便会选择下标对齐dp[2]就代表解码s[2]后的解码方法这样不容易出错代码也会更整洁。

4、填表顺序

ns.size();//下表映射vectorintdp(n1);//2、初始化dp[0]和dp[1]//初始化dp[0]是为了在后续填dp[2]如果只有两个数第二个数解码成功//dp[1]已经赋值可以加但如果组合解码成功dp[0]0回会影响最后的结果//我们需要考虑到这点都是为了更好的填表dp[0]1;//不为0则dp[1]1,否则为0dp[1]s[0]!0;for(int

i2;in;i){//判断条件成功则加dp[i-1],失败则是0因为默认即是0if(s[i-1]!0)

dp[i]dp[i-1];int

t(s[i-2]-0)*10s[i-1]-0;if(t10t26)

dp[n];}