【动态规划】斐波那契数列模型_解码方法_C++（medium）

题目链接：leetcode解码方法

---

目录

题目解析：

算法原理

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

编写代码

---

题目解析：

题目让我们求解码?方法的?总数

由题可得：

0和有前导0（比如06、08、04）的都不能解码；

我们先用实例来分析题目：

实例一：s=“1 2”

那么1和2可以单独解码；

也可以是两个一起‘12’解码；

所以这里解码方法为2；

实例二：s=“0 6”

这里0不能解码，06也不能解码

所以这里解码方法为0；

---

算法原理:

1.状态表示

先创建一个dp表

首先先思考dp表里面的值所表示的含义（是什么？）

dp[i]表示到i位置一共有多少种解码方法；

这种状态表示怎么来的？

1.经验+题目要求

经验：以i位置为结尾，

题目让我们求解码总数，那么这里我们可以dp[i]来表示。

2.状态转移方程

dp[i]等于什么？

用之前或者之后的状态，推导出dp[i]的值；

根据最近的最近的一步，来划分问题

这里我们分两种情况：

情况一：i位置单独解码；

1.解码成功

当s[i]不等于0时，就可以解码；

此时只要在dp[i-1]的方法后面加上一步就可以；

比如：1 2 1 3 4

1 2 1 3--->1 2 1 3 4

此时i位置的方法数为dp[i-1];

2.解码失败

当s[i]等于0时，解码失败；

解码方法为0；

情况一：i与i-1位置解码；

1.解码成功

当10<=s[i-1]*10+s[i]<=26时，就可以解码；

这里因为不能是06、04等这种有前导0的，所以这里的s[i-1]*10+s[i]一定要大于等于10；

此时i位置的方法数为dp[i-2];

2.解码失败

当【10<=s[i-1]*10+s[i]<=26】不是这个范围时，解码失败；

综上，状态转移方程：

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

3.初始化

(保证填表的时候不越界)

由状态转移方程得：

在i=0、1的时候越界，所以这里要对这两个数初始化；

这里还要注意处理一下边界问题：

当s只有一个数的时候，就直接返回dp[0]就好了。

4.填表顺序

（为了填写当前状态的时候，所需要的状态已经计算过了）

这里所需要的状态是：dp[i-1]、dp[i-2]

这几个数都是在i之前的，

所以我们这里是从左向右填表；

5.返回值

（根据题目要求和状态表示）

综上分析：

返回值为：dp[n-1]

---

编写代码:

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

    int n=s.size();
    vector<int> dp(n);

    if(s[0]!='0')
        dp[0]=1;
    else
        return 0;
    //处理边界情况
    if(n==1)
    {
        return dp[0];
    }
    
    if(s[1]!='0')
        dp[1]+=1;
    int cnt=(s[0]-'0')*10+(s[1]-'0');
    if(cnt<=26&&cnt>=10)
        dp[1]+=1;

    for(int i=2;i<n;i++)
    {
        if(s[i]!='0')
            dp[i]+=dp[i-1];

        int cnt=(s[i-1]-'0')*10+(s[i]-'0');
        if(cnt<=26&&cnt>=10)
            dp[i]+=dp[i-2];
 

    }

    return dp[n-1];


    }
};