算法---动态规划-3（解码方法）

1. 题目解析

题目地址：点这里

2. 讲解算法原理

1. 首先，通过字符串s的大小确定字符串的长度为n，并创建一个长度为n的动态规划数组dp。

2. 处理特殊情况：如果字符串s的长度为1，那么只有当s[0]不等于零时才有一种解码方法，否则没有解码方法。

3. 初始化动态规划数组dp的前两个元素dp[0]和dp[1]。

• 如果s[0]不等于零，那么dp[0]初始化为1，表示第一个字符可以单独解码。
• 如果s[0]和s[1]都不等于零，那么dp[1]初始化为1，表示前两个字符可以分别单独解码。
• 如果前两个字符可以组成一个大于等于10且小于等于26的数字，那么dp[1]再加1，表示前两个字符可以作为一个整体解码。

4. 接下来，从下标2开始填表。对于每个下标i，计算dp[i]的值：

• 定义两个变量a和b，初始化为0。
• 如果当前字符s[i]不等于零，说明它可以单独解码，将dp[i-1]的值赋给a。
• 将前两个字符s[i-1]和s[i]组成的两位数d计算出来。
  • 如果d大于等于10且小于等于26，说明这两个字符可以作为一个整体解码，将dp[i-2]的值赋给b。
• 计算dp[i]的值为a+b，表示当前字符可以单独解码或与前一个字符组成一个整体解码的方法数量。

5. 最后，返回动态规划数组dp的最后一个元素dp[n-1]，即整个字符串的解码方法数量。

3. 编写代码

class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        vector<int> dp(n);
        //处理特殊情况
        if(n==1 ) 
        {
            if(s[0]!='0') return 1;
            else return 0;
        }
        //初始化(下标0和1)
        if(s[0]!='0') dp[0]=1;
        else dp[0]=0;

        if(s[0]!='0' && s[1]!='0')dp[1]+=1;
        int t=(s[0]-'0')*10+(s[1]-'0');
        if(t>=10 && t<=26) dp[1]+=1;
        //填表
        for(int i=2;i<n;i++)
        {
            int a=0,b=0;
            int d=(s[i-1]-'0')*10+(s[i]-'0');
            if(s[i]!='0') a=dp[i-1];
            if(d>=10 && d<=26) b=dp[i-2];
            dp[i]=a+b;
        }  
        return dp[n-1];
    }
};