LeetCode-91. 解码方法

我就是我 2024-03-24 16:44 26阅读 0赞

#### 目录 ####

*   *  动态规划

题目来源  
[91. 解码方法][91.]

### 动态规划 ###

*  1.确定dp数组以及下标的含义

dp\[i\]表示前i个数字一共有多少种解码方式，那么，dp\[n\]就表示前n个数字一共有多少种不同的解码方式

*  2.确定递推公式

对于字符串 s 的任意位置 i 而言，其存在三种情况：  
只能由位置 i 的单独作为一个item，设为 a，转移的前提是 a 的数值范围为 \[1,9\]，转移逻辑为 dp\[i\]=dp\[i−1\]。  
只能由位置 i 的与前一位置（i-1）共同作为一个 item，设为 b，转移的前提是 b 的数值范围为 \[10,26\]，转移逻辑为 dp\[i\]=dp\[i−2\]。  
位置 i 既能作为独立 item 也能与上一位置形成 item，转移逻辑为 dp\[i\]=dp\[i−1\]+dp\[i−2\]。

dp[i]=dp[i−1],1⩽a≤9
    dp[i]=dp[i−2],10⩽b⩽26
    dp[i]=dp[i−1]+dp[i−2],1⩽a≤9,10⩽b⩽26

*  3.dp数组如何初始化

dp\[0\] = 1，解码前0个数的方案数为1。  
dp\[0\]代表前0个数字的方案数，这样的状态定义其实是没有实际意义的，但是dp\[0\]的值需要保证边界是对的，即dp\[1\]和dp\[2\]是对的。比如说，第一个数不为0，那么解码前1个数只有一种方法，将其单独解码，即dp\[1\] = dp\[1 - 1\] = 1。解码前两个数，如果第1个数和第2个数可以组合起来解码，那么dp\[2\] = dp\[1\] + dp\[0\] = 2，否则只能单独解码第2个数，即f\[2\] = f\[1\] = 1。因此，在任何情况下f\[0\]取1都可以保证f\[1\]和f\[2\]是正确的，所以f\[0\]应该取1。

*  4.确定遍历顺序

从递归公式dp\[i\]=dp\[i−1\]+dp\[i−2\]中可以看出，遍历的顺序一定是从左到右遍历

*  5.举例推导dp数组

以s = "226"例

![在这里插入图片描述][bef64602bf23412f95bca926d912142f.png]

代码实现

class Solution {
        
        public int numDecodings(String s) {
        
            int n = s.length();
            int[] dp = new int[n+1];
            dp[0] = 1;  //如果只有一个数 2的时候,那么dp[i] = dp[i-1] 就为1
            for(int i = 1;i<dp.length;i++){
        
                int a = s.charAt(i-1)-'0';
                if(a>=1 && a<=9){
        
                    dp[i] = dp[i-1];   //单独解码s[i - 1]
                }
                if(i>=2){
        
                    int b = (s.charAt(i-2)-'0')*10+s.charAt(i-1)-'0';
                    if(b>=10 && b<=26){
        
                        dp[i] += dp[i-2];   //将s[i - 2] 和 s[i - 1]组合解码
                    }
                }
            }
            return dp[dp.length-1];
        }
    }

![在这里插入图片描述][917dfcee8e9949b68dcf097a71ac7bfc.png]

[91.]: https://leetcode.cn/problems/decode-ways/
[bef64602bf23412f95bca926d912142f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/bf1464fdaf4a4e6e96ea390bccb661a1.png
[917dfcee8e9949b68dcf097a71ac7bfc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/424184cff8ea414b85211b4bc943e9c1.png