题目链接：91. 解码方法 - 力扣（LeetCode）
https://leetcode.cn/problems/decode-ways/description/
一、题目解析
题目：
题目大意：从题目中我们可以知道，解码就是在字符串s中由‘1’到‘26’的字符可以转化成字母A到Z，在所给的一个字符串中我们有很多种解码方式，可以解出不一样的答案。
解析：
- 我们在解码时，可以单个单个解码，也可以由两个字符组合解码，但是需要注意，我们单个字符时不可以是0，两个字符组合解码时需要大于等于10小于等于26
- 拿题例子来讲:我们不可以以0开头，即不可以是06，也不可以是60，因为大于26，无法解码，第二位如果是0，那第一位只能是1或2。
二、算法原理
1、状态表示
我们在状态标识的时候，一般都会创建一个数组dp，也就是我们所说的dp表，我们要做的就是把每一个状态的值填入这个表内，最终这个表内的某一个值可能就是我们要返回的值。
状态简单理解就是dp表内某一个值代表的含义。
如何确定状态表示
- 题目要求
简单的题目里一般会给出
- 经验+题目要求
越学越深入，动态规划也是熟能生巧，在题目中没有明显给出的时候，我们就要凭借自己做题的经验来确定，所以就需要我们大量的做题。
- 分析问题的过程中，发现重复子问题
分析问题的过程中把重复子问题抽象成我们的状态表示，这个更难理解，一切的基础都是我们先对动态规划算法熟练运用。我也不懂，我们慢慢来。
综上：我们通常会以一个位置为结尾或者开始求得我们想要的答案
那我们的这道题得状态表示是什么样的：我们根据经验所判断，我们可以以某个位置为结尾
状态表示为：dp[i]：解码到i时的解码方法数
2、状态转移方程
确定状态表示之后我们就可以根据状态标识推出状态转移方程
状态转移方程是什么？
不讲什么复杂的，简单来说状态转移方程就是 dp[i]等于什么 dp[i]=？
这个就是状态转移方程，我们要做的，就是推出dp[i]等于什么
我们根据状态表示再结合题目+经验去推理转移方程，这一步也是我们整个解题过程中最难的一步
我们根据题解析可以知道，我们可以单解和组合解，先看图：
在解之前，我们需要判断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]后的解码方法，这样不容易出错，代码也会更整洁。
所以我们在初始化时，要dp开空间大小比s字符串大1
4、填表顺序
我们既然是以一个位置为结尾，那我们就应该从左到右依次填写
5、返回值
最后返回dp[n],即最后一个值
三、编写代码
class Solution {
public:
int numDecodings(string s) {
//1、创建dp表
int n=s.size();
//下表映射
vector<int>dp(n+1);
//2、初始化dp[0]和dp[1]
//初始化dp[0]是为了在后续填dp[2]，如果只有两个数，第二个数解码成功，
//dp[1]已经赋值，可以加，但如果组合解码成功，dp[0]=0回会影响最后的结果
//我们需要考虑到这点，都是为了更好的填表
dp[0]=1;
//不为'0'则dp[1]=1,否则为0
dp[1]=s[0]!='0';
for(int i=2;i<=n;i++)
{
//判断条件，成功则加dp[i-1],失败则是0，因为默认即是0
if(s[i-1]!='0') dp[i]+=dp[i-1];
int t=(s[i-2]-'0')*10+s[i-1]-'0';
if(t>=10&&t<=26) dp[i]+=dp[i-2];
}
//返回值
return dp[n];
}
};
