【动态规划】：泰波那契模型

【动态规划】：泰波那契模型_解码方法

朋友们、伙计们，我们又见面了，本专栏是关于各种算法的解析，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

C 语言专栏：C语言：从入门到精通

数据结构专栏：数据结构

个人主页：stackY、

C + + 专栏：C++

Linux 专栏：Linux

1. 题目解析

2. 算法原理

2.1 状态表示

2.2 状态转移方程

2.3 初始化

2.4 填表顺序

2.5 返回值

3. 代码实现

4. 算法复杂度

5. 优化边界情况以及初始化

5.1 优化之后代码

1. 题目解析

Leetcode91.解码方法：https://leetcode.cn/problems/decode-ways/description/

一条包含字母 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 位 的整数。

示例 1：
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2：
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 3：
输入：s = "06"
输出：0
解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。
提示：

1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。

本题采用动态规划的思想，以某一位置为开始，或者以某一位置为结束，要注意的是：

例如：

06没有解码方式，因为单独的0不能解码，并且06组合起来也不能解码，06和6并不等价。

60也没有解码方式，6单独有解码方式，但是0没有，并且二者结合60也没有解码方式。

262有两种解码方式，依次单独解码(1)，26组合解码(2)，但是62组合没有解码方式。

那么就表明：

一个数要能单独解码就要在'1' ~ '9' 之间

两个数组合一起能解码就要在'10' ~ '26' 之间

2. 算法原理

2.1 状态表示

根据题目要求：

要求的是总共的解码数，那么假设一共有i个数

那么我们以i位置为结尾时，所得的解码的方法就是要求的解码方法总数。

因此：dp[i] 就表示解码的方法数。

2.2 状态转移方程

根据最近的一步划分问题：

dp[i]位置的解码数就是：①s[i]单独解码数

②s[i-1]和s[i]组合起来的解码数

①如果s[i]能单独解码，那么此时的解码数就是dp[i-1]时的解码数，如果不能单独解码，那么之前的工作都作废了，总的解码数为0的。

②如果s[i-1]和s[i]组合起来能解码，那么此时的解码数就是dp[i-2]时的解码数，如果组合起来不能解码，那么就为0。

因此如果两种方式都可以解码成功：dp[i] = dp[i-1] + dp[i-2]

2.3 初始化

为了防止越界，求dp[i]就要知道dp[i-1]和dp[i-2]，所以需要将dp[0]和dp[1]初始化

dp[0]就是s[0]位置的解码数，那么只有0和1两种情况，如果s[0]能单独解码，就是1，不能则是0。

dp[1]就是s[1]位置的解码数，这里存在两种情况，如果s[0]和s[1]能单独解码就算一种，如果s[0]和s[1]组合起来能解码也是一种，如果s[1]单独都不能解码就是0。

因此dp[1]的解码方法是0或1或2。

2.4 填表顺序

从左向右

2.5 返回值

dp[n-1]

3. 代码实现

class Solution 
{
public:
    int numDecodings(string s) 
    {
        int n = s.size();
        // 1. 创建dp表
        vector<int> dp(n);   

        // 2. 初始化
        dp[0] = s[0] != '0';
        // 边界情况
        if(n == 1) return dp[0];

        if(s[0] != '0' && s[1] != '0') dp[1] += 1;
        int ret = (s[0] - '0')*10 + s[1] - '0';
        if(ret >= 10 && ret <= 26) dp[1] += 1;
        
        // 3. 填表
        for(int i = 2; i<n; i++)
        {
            // 单独解码
            if(s[i] != '0') dp[i] += dp[i-1];
            int ret = (s[i-1] - '0')*10 + s[i] - '0';
            // 组合解码
            if(ret >= 10 && ret <= 26) dp[i] += dp[i-2];
        }

        // 4. 返回值
        return dp[n-1];
    }
};

4. 算法复杂度

时间复杂度：O(N)

空间复杂度：O(N)

5. 优化边界情况以及初始化

通过上面的代码可以发现：初始化部分与填表部分逻辑类似代码冗余，所以可以做以优化

我们在创建dp表时可以多创建一个空间，只需要对这个空间进初始化就可以优化繁琐的初始化过程：

既然多开了一个空间，那么就需要注意两个问题：

1. 初始化虚拟节点的值，要保证后面的填表是正确的；

2. 下标映射的关系。

下面，我们分别来对这两个问题进行研究：

1. 初始化虚拟节点的值，要保证后面的填表是正确的

因为我们多开了一个空间，这个空间的值也就意味着后面的值正确与否，我们需要根据题目要求和状态表示来初始化这个虚拟空间的值：

状态表示：dp[i]表示解码方法数

那么这个虚拟空间的值应该被设置为1 -> dp[0] = 1

那么为什么呢？

在计算dp[2]时，如果可以与前一个组合起来解码，那么需要加上dp[i-2]，这样就正好是一种方法。

2. 下标映射的关系

由于我们多创建了一个空间，那么在填表的时候s中的下标就要统一减一。

5.1 优化之后代码

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        // 多开一个空间
        vector<int> dp(n + 1);
        // 初始化
        dp[0] = 1;
        dp[1] = s[1 - 1] != '0';

        for(int i = 2; i<=n; i++)
        {
            // s的下标要对应-1
            if(s[i - 1] != '0') dp[i] += dp[i-1];
            int ret = (s[i-2] - '0')*10 + s[i - 1] - '0';
            if(ret >= 10 && ret <= 26) dp[i] += dp[i-2];
        }
        //多开一个空间所以返回第n个位置即可
        return dp[n];
    }
};