本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。 通过本专栏的深入学习，你可以了解并掌握算法。

💓博主csdn个人主页：小小unicorn
⏩专栏分类：动态规划专栏
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

题目来源

本题来源为：

Leetcode91. 解码方法

题目描述

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”

要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：

“AAJF” ，将消息分组为 (1 1 10 6)
“KJF” ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回解码 方法的总数 。
题目数据保证答案肯定是一个 32 位 的整数

题目解析

解码按照规则解码即可，但是前导0不可解码。

算法原理

1.状态表示

经验+题目要求：
以i位置为结尾…

对于本题而言就是：
dp[i]表示：以i位置为结尾时，解码方法的总数

2.状态转移方程

在推方程之前，我们先画一下解码的情况：

分为单独解码和与前一个位置一起解码两种情况：

而单独解码和一起解码又要分为两种情况，成功和失败。
为什么会失败呢？
举个例子：

2和5可以一起解码，也可以分开解码，但到0位置时，就会解码错误，自己单独不能解码，要是与后面的6结合，

会出现之前说的前导0情况，也会解码错误。

因此，本题的状态转移方程为：

dp[i] = dp[i-1]+ dp[i-2]

3.初始化

本题初始化要在下标为0位置与下标为1位置进行初始化：

  dp[0]=s[0]!='0';
     //处理边界条件：
   if(n==1)
     return dp[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;

4.填表顺序

根据状态转移方程，我们计算dp[i]位置的值需要i-1与i-2位置的值，因此我们的填表顺序为：从左往右

5.返回值

我们要解码到最后一个位置，因此：返回dp[n-1]

代码实现

class Solution 
{
public:
    int numDecodings(string s) 
    {
        // 1.创建dp表
        // 2.初始化
        // 3.填表
        // 4.返回值

        int n=s.size();
        vector<int> dp(n);
        dp[0]=s[0]!='0';
        //处理边界条件：
        if(n==1)
        return dp[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++)
        {
            //处理单独编码：
            if(s[i]!='0')
            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];
    }
};