leetcode 91. Decode Ways | 91. 解码方法（动态规划）

不念不忘少年蓝@ 2022-09-06 00:17 157阅读 0赞

## 题目 ##

[https://leetcode.com/problems/decode-ways/][https_leetcode.com_problems_decode-ways]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

dp 问题，首先用模拟的办法试一下，理清楚状态转移关系。

当走到 i 位置时，i 有两种选择：

*  i 不与 i-1 组合，此时，只要 i 位置不是 0，总的组合方式等于前一个状态的所有组合方式
 *  i 与 i-1 组合，此时，只要前一个状态是非组合，且组合之后小于等于 26，则总的组合方式等于前一个非组合的方式数量

看草稿：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

class Solution { 
        public int numDecodings(String s) { 
            int L = s.length();
            int[][] dp = new int[L][2]; // dp[不组合的有效数量][与i-1组合的有效数量]
            dp[0][0] = s.charAt(0) == '0' ? 0 : 1;
            // dp[0][1] = 0;
            for (int i = 1; i < L; i++) { 
                int n1 = s.charAt(i - 1) - '0';
                int n2 = s.charAt(i) - '0';
                if (n2 != 0) {  // i非0，才能不组合
                    dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
                }
                if (n1 != 0 && 10 * n1 + n2 <= 26) {  // i-1非0，i可尝试和i-1组合
                    dp[i][1] = dp[i - 1][0];
                }
            }
            return dp[L - 1][0] + dp[L - 1][1];
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_decode-ways]: https://leetcode.com/problems/decode-ways/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/6f334915a3864968b4bb62ccc96d9328.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/f49fc8464cc4493f9bb8db919af68d27.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/a975c1c8d8b54daabcc449bf77ead189.png