1. 解码方法
题目链接：
91. 解码方法 - 力扣（LeetCode）
https://leetcode.cn/problems/decode-ways/description/
2. 题目解析
1. 对字母
A - Z进行编码1-26
2.
11106可以解码为1-1-10-6或者11-10-6, 但是11-1-06不能解码
3. 0n不能解码
4. 字符串非空，返回解码方法的总数
3. 算法原理
1. 状态表示：以i位置为结尾
dp[i]表示：以i位置为结尾时，解码方法的总数
创建dp(n+1)的dp表，第一个位置用作虚拟位置，对应的第i个位置映射的下标也为i，只用初始化第一个dp表的位置即可
2. 状态转移方程
根据最近的一步来划分问题：
1. s[i]位置单独解码
a.解码成功，1<=a<=9，dp[i-1]
b.解码失败，0
2. s[i-1] 与 s[i]进行解码
a.解码成功，10<=b*10+a<=26，dp[i-2]
b.解码失败，0
本题的状态转移方程是：dp[i] = dp[I-1] + dp[I-2]（解码成功的情况下,解码失败即为0）
3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行
dp[i]表示：以i位置为结尾时，解码方法的总数
1. 以0位置为结尾，说明只有一个字符,一个字符的解码方案数要么是1，要么是0，当dp[0]为1<=a<=9时，解码成功，否则失败
2.以1位置为结尾，说明有两个字符,两个字符的解码方案数要么是1，要么是0，要么是2
4. 填表顺序
本题的填表顺序是：从左到右
5. 返回值 ：题目要求 + 状态表示
本题的返回值是：直接返回dp[n-1]
4. 代码
动态规划的固定四步骤：1. 创建一个dp表
2. 在填表之前初始化
3. 填表（填表方法：状态转移方程）
4. 确定返回值
class Solution {
public:int numDecodings(string s) {int n=s.size();//创建dp表vector<int>dp(n);//在填表之前初始化dp[0]=s[0]!='0';//初始化0位置为结尾，dp[0]在1~9之间//处理边界化if(n==1) return dp[0];//如果只有一位数的话就直接返回//如果第一个位置的值和第二个位置的值都可以单独编码if(s[0]!='0' && s[1]!='0') dp[1]+=1;//如果需要进行组合解码 10<=b*10+a<=26int t=(s[0]-'0')*10+s[1]-'0';//前两个位置所表示的数if(t>=10 && t<=26) dp[1]+=1;//0~9之间解码会出现01，02之类的// 填表for(int i=2;i<n;i++){//如果单独编码if(s[i]<='9'&&s[i]>='1') dp[i]+=dp[i-1];//如果和前面的一个数联合起来编码int t=(s[i-1]-'0')*10+s[i]-'0';if(t>=10&&t<=26) dp[i]+=dp[i-2];}return dp[n-1];}
};完结撒花~
