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

动态规划之解码方法

91. 解码方法
- 解法1
- 解法2

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];
    }
};