动态规划之解码方法【LeetCode】

简介: 动态规划之解码方法【LeetCode】


91. 解码方法

91. 解码方法

解法1

状态表示这是最重要的):dp[i]表示以第i个字符为结尾,解码方法的总数。

状态转移方程最难的):根据最近的一步来划分问题,从右向左思考,我们需要考虑s[i]和s[i-1]是单独为一个字符形成两个数字,还是合并为一个字符形成为一个数字。

  如果s[i]和s[i-1]是单独为一个字符形成两个数字,那么dp[i]的值就是dp[i-1]的值;

  如果s[i]和s[i-1]合并为一个字符形成为一个数字,那么dp[i]的值就是dp[i-2]的值。因为s[i]和s[i-1]都形成一个数字了,再dp[i]往前就是就是dp[i-2]了。

  因为单独一个0不能解码,所以当s[i]和s[i-1]是单独为一个字符时,若s[i]为’0’,dp[i] = 0;

  如果形成的两位数数字不在[10, 26]区间内的话(因为前导0不能编码,所以不是[1, 26]),所以当s[i]和s[i-1]合并为一个字符时,若超出这个范围了,dp[i] = 0;

初始化:因为我们得状态转移方程里面包含dp[i-1]和dp[i-2],所以我们需要初始化dp[0], dp[1],以免越界及无法计算。dp[0]就只有一个,我们只需要判断它是不是不为’0’即可,dp[0] = s[0] != '0';

  dp[1]的话有两种情况,单独为两个数1且分开成两个数,单独为一个数需要判断形成的这一个数是否在[10, 26]这个范围里面;分别为两个数只需要判断s[0]和s[1]是不是都不为’0’。

填表顺序:当我们求解当前问题时,需要知道所需较小子问题的解,这就需要我们先求解得到较小子问题的解,这就是填表顺序。我们这道解法是从左向右填表。

返回值return dp[n-1];

代码实现:

class Solution {
public:
    int numDecodings(string s) {
        // 创建dp表
        int n = s.size();
        vector<int> dp(n);
        // 初始化
        dp[0] = s[0] != '0';
        // 处理边界问题
        if(1 == n) return dp[0];
        if(s[0] != '0' && s[1] != '0') dp[1] = 1;
        int count = (s[0]-'0')*10 + s[1]-'0';
        if(count >= 10 && count <= 26) dp[1]++;
        // 填表
        for(int i = 2; i < n; i++)
        {
            if(s[i] != '0') dp[i] += dp[i-1];
            int count1 = (s[i-1]-'0')*10 + s[i]-'0';
            if(count1 >= 10 && count1 <= 26) dp[i] += dp[i-2];
        }
        // 返回
        return dp[n-1];
    }
};

解法2

当我们观察解法1中的代码时,我们会发现如下图两个红圈中的代码是类似的,那么是否可以简化代码呢?

我们可以可以将解法1中的dp数组整体向右移动一个元素的位置, 解题思路和解法1一样,如此一来我们只需要初始化新增加的dp[0]和dp[1](解法1中dp数组的dp[0])。

dp[1]的初始化跟解法1一样:dp[1] = s[0] != '0';

但是dp[0]由于没有对应的字符,我们该如何给它赋值呢?

按理来说既然没有对应字符,那么我们应该将dp[0]初始化为0。如果这样的话,我们得代码将是这样的:

class Solution {
public:
    int numDecodings(string s) {
        // 创建dp表
        int n = s.size();
        vector<int> dp(n+1);
        // 初始化
        dp[0] = 0;
        dp[1] = s[0] != '0';
        
        // 填表
        for(int i = 2; i <= n; i++)
        {
            if(s[i-1] != '0') dp[i] += dp[i-1];
            int count1 = (s[i-2]-'0')*10 + s[i-1]-'0';
            if(count1 >= 10 && count1 <= 26) dp[i] += dp[i-2];
        }
        // 返回
        return dp[n];
    }
};

在我们将注意力放在红圈里面,在计算dp[2]时,我们会发现,明明s[0]和s[1]组成的数字已经在[10, 26]这个范围之中了,但是dp[i] += dp[i-2]这个代码不能让dp[i]也就是dp[2]有任何变化,因为dp[i-2]也就是dp[0]被初始化为0了,但是应该使得dp[i]也就是dp[2]加上1的。所以,在我们初始化时,我们要将dp[0]初始化为1。

代码实现:

class Solution {
public:
    int numDecodings(string s) {
        // 创建dp表
        int n = s.size();
        vector<int> dp(n+1);
        // 初始化
        dp[0] = 1;
        dp[1] = s[0] != '0';
        
        // 填表
        for(int i = 2; i <= n; i++)
        {
            if(s[i-1] != '0') dp[i] += dp[i-1];
            int count1 = (s[i-2]-'0')*10 + s[i-1]-'0';
            if(count1 >= 10 && count1 <= 26) dp[i] += dp[i-2];
        }
        // 返回
        return dp[n];
    }
};

     😄 创作不易,你的点赞和关注都是对我莫大的鼓励,再次感谢您的观看😄

相关文章
|
3天前
|
算法 Python
LeetCode 常用方法
LeetCode 常用方法
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(4)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
4天前
|
存储 算法
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(1)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
7天前
|
SQL 算法 数据挖掘
深入解析力扣183题:从不订购的客户(LEFT JOIN与子查询方法详解)
深入解析力扣183题:从不订购的客户(LEFT JOIN与子查询方法详解)
|
7天前
|
SQL 算法 大数据
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
|
7天前
|
存储 算法 数据挖掘
力扣174题动态规划:地下城游戏(含模拟面试)
力扣174题动态规划:地下城游戏(含模拟面试)
|
7天前
|
算法 数据挖掘 大数据
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
|
8天前
|
存储 算法 数据可视化
【模拟面试问答】深入解析力扣164题:最大间距(桶排序与排序方法详解)
【模拟面试问答】深入解析力扣164题:最大间距(桶排序与排序方法详解)
|
8天前
|
存储 算法 数据可视化
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
|
8天前
|
存储 算法 数据可视化
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)