526互联

【DP】LeetCode 91. 解码方法

发布时间 2023-04-23 09:25:50作者: Frodo1124

题目链接

91. 解码方法

思路

分析动态规划题目的时候只需要考虑最后一个阶段，因为所有的阶段转化都是相同的，考虑最后一个阶段容易发现规律

在数组的动态规划问题中，一般 dp[i] 都是表示以 nums 以前 i 个元素组成（即 nums[i - 1]）的状态；dp[i][j] 分别表示以 nums1 前 i 个元素（即 nums1[i - 1]）组成和以 nums2 前 j 个元素（即 nums2[j - 1]）组成的状态，以此类推

字符串也是个数组，是字符数组

表示状态

状态表示就是靠猜，但是会有猜的套路，一般都是通过最终结果和数组数量来猜

这道题和【DP】LeetCode 剑指 Offer 46. 把数字翻译成字符串非常像，但是要复杂一些，原因是46题中0也能映射为一个字符，而本题中的0却是无效的，这就需要在解题中考虑前导0，而不能直接暴力的

找状态转移方程

思考的方向是：大问题的最优解怎么由小问题的最优解得到

边界处理

dp[0] = 1;
dp[1] = s.charAt(0) == '0' ? 0 : 1;

空间优化

因为 \(dp[i]\) 只和 \(dp[i - 1]\) 还有 \(dp[i - 2]\) 有关，所以可以用两个单变量 \(preDp1\) 和 \(preDp2\) 分别代表 \(dp[i - 1]\) 还有 \(dp[i - 2]\)，在遍历过程中滚动更新

代码

dp数组版

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if(n < 1){
            return 0;
        }

        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0' ? 0 : 1;

        for(int i = 2; i <= n; i++){
            int c = s.charAt(i - 1);
            int pre = s.charAt(i - 2);

            // s[i - 1] 能单独成字母
            if('1' <= c && c <= '9'){
                dp[i] += dp[i - 1];
            }
            // s[i - 1] 和 s[i - 2] 能组合成字母
            if(pre == '1' || (pre == '2' && c <= '6')){
                dp[i] += dp[i - 2];
            }
        }

        return dp[n];
    }
}

空间优化版

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if(n < 1){
            return 0;
        }

        int preDp1 = 1;
        int preDp2 = s.charAt(0) == '0' ? 0 : 1;
        int current = 0;

        for(int i = 2; i <= n; i++){
            int c = s.charAt(i - 1);
            int pre = s.charAt(i - 2);

            // s[i - 1] 能单独成字母
            if('1' <= c && c <= '9'){
                current += preDp2;
            }
            // s[i - 1] 和 s[i - 2] 能组合成字母
            if(pre == '1' || (pre == '2' && c <= '6')){
                current += preDp1;
            }
            preDp1 = preDp2;
            preDp2 = current;
            current = 0;
        }

        return preDp2;
    }
}