【动态规划: 线性dp】解码方法

文章目录

• 题目解析
• 算法原理
• • 确定状态表示
  • 确定状态转移方程
  • 初始化
  • 确定填表顺序
  • 确定返回值
  • 细节问题
• 代码实现
• • 普通动态规划
  • 优化初始化版本
  • 空间优化版本

题目链接：91. 解码方法

---

题目解析

动态规划（Dynamic programming，简称 DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费不必要的时间。

通常的解决步骤有五步：

1. 确定状态表示/dp表的含义
2. 确定状态转移方程/递推公式
3. 初始化
4. 确定填表顺序
5. 确定返回值

一条包含字母A-Z的消息通过以下映射进行了编码：

• "1" -> 'A'

• "2" -> 'B'

• ...

• "25" -> 'Y'

• "26" -> 'Z'

然而，在解码已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（"2"和"5"与"25"）。

例如，"11106"可以映射为：

• "AAJF"，将消息分组为(1, 1, 10, 6)
• "KJF"，将消息分组为(11, 10, 6)
• 消息不能分组为(1, 11, 06)，因为"06"不是一个合法编码（只有 “6” 是合法的）。

注意，可能存在无法解码的字符串。

给你一个只含数字的非空字符串s，请计算并返回解码方法的总数。如果没有合法的方式解码整个字符串，返回0。

题目数据保证答案肯定是一个32 位的整数。

示例 1：

• 输入：s = “12”
• 输出：2
• 解释：它可以解码为 “AB”（1 2）或者 “L”（12）。

示例 2：

• 输入：s = “226”
• 输出：3
• 解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

示例 3：

• 输入：s = “06”
• 输出：0
• 解释：“06” 无法映射到 “F” ，因为存在前导零（“6” 和 “06” 并不等价）

---

算法原理

确定状态表示

状态表示/dp表含义可以从题目要求找出，也可以从重复子问题中找出。

通常可以确定以 i 位置为起始或者以 i 位置为结尾。

本题采用后者，因此状态表示：dp[i] 表示解码到 i 位置时，解码方法的总数。

确定状态转移方程

对于s[i]，解码的思路：

1. 若s[i]可以单独解码，则有1 <= s[i] <= 9，此时解码方法数和前一个字符的解码方法数一样，即dp[i] = dp[i - 1]
2. 若s[i]与前一个字符s[i-1]合并解码，则当满足条件10 <= b*10 + a <= 26(其中 b 为 s[i-1] 的 ASCII 码转为整数类型的值，a 同理) 时，此时由于和前一个字符组合了，解码方法数就与前两个字符的解码方法一样，即dp[i] = dp[i-2]
3. 综合以上两种情况，可以得出状态转移方程：dp[i] = dp[i-1] + dp[i-2]

初始化

• 对于第一个字符的初始化，我们只需要考虑是否满足1 <= ch <= 9即可
• 对于第二个字符的初始化，则需要分两种情况考虑：先考虑能否单独解码（条件是第一个字符和自己都必须在[1,9]区间内），若可以单独解码，方法数就加一；再考虑与前一个字符组合解码，组合后的字符需要满足10 <= ch <= 26方法数才能加一

• 可将第二个字符的初始化优化：dp表整体向右移动一个单位，使得第二个字符的 dp 值在数组中是第三个位置，这样就可以放到填表中操作

确定填表顺序

从字符串的左边开始向右解码，因此填表顺序是从左往右。

确定返回值

我们需要返回解码的方案总数，也就是将整个字符串解码后得到的解码方法数，即dp[n-1]。

细节问题

• 考虑边界情况：当题目所给的字符串长度只有 1 怎么处理？

---

代码实现

普通动态规划

classSolution{publicintnumDecodings(Strings){// 预处理char[]ss=s.toCharArray();intn=ss.length;// 创建dp表(dp[i]表示到位置i时的解码方法数)int[]dp=newint[n];// 初始化第一个字符(若为0——即有前导零,解码方法数是0)dp[0]=ss[0]=='0'?0:1;// 边界情况(消息长度只有1)if(n==1){returndp[0];}// 初始化第二个字符// 考虑第一种情况:独自解码(必须满足1<=ch<=9);同时也必须保证ss[0]非0if(ss[0]!='0'&&ss[1]!='0'){dp[1]+=1;}// 考虑第二种情况:和前一个字符组合解码(组合后的字符必须满足10<=char<=26)inttemp=(ss[0]-'0')*10+ss[1]-'0';if(temp>=10&&temp<=26){dp[1]+=1;}// 从左往右填dp表for(inti=2;i<n;i++){// 先考虑ss[i]是否为0,若不为0就表示可以独自解码if(ss[i]!='0'){dp[i]+=dp[i-1];}// 再考虑ss[i]与ss[i-1]组合解码,判断组合后的字符是否满足条件temp=(ss[i-1]-'0')*10+ss[i]-'0';if(temp>=10&&temp<=26){dp[i]+=dp[i-2];}}// 返回结果(将整个字符串解码,总方法数为dp[n-1])returndp[n-1];}}

优化初始化版本

优化版本主要针对第二个字符的初始化，将这部分代码放到 “填表” 里。

以下是细节问题：

• 由于这个版本的 dp表是往右移动了一个单位的，因此在填表时，访问字符串的下标都要减一
• 同时也要注意 dp表左边多出一个位置dp[0]不再对应s[0]，并且由于状态转移方程dp[i] = dp[i-1] + dp[i-2]，当 i 取 2 时会用到dp[0]，本题将其初始化为 1 即可。
• 在填表时也要注意循环边界可取i == n。

classSolution{publicintnumDecodings(Strings){// 预处理char[]ss=s.toCharArray();intn=ss.length;// 创建dp表(dp[i]表示到位置i时的解码方法数),往右移动一个单位int[]dp=newint[n+1];// 初始化第一个位置的值为1dp[0]=1;// 初始化第一个字符(若为0——即有前导零,解码方法数是0)dp[1]=ss[0]=='0'?0:1;// 从左往右填dp表for(inti=2;i<=n;i++){// 先考虑ss[i]是否为0,若不为0就表示可以独自解码if(ss[i-1]!='0'){dp[i]+=dp[i-1];}// 再考虑ss[i]与ss[i-1]组合解码,判断组合后的字符是否满足条件inttemp=(ss[i-2]-'0')*10+ss[i-1]-'0';if(temp>=10&&temp<=26){dp[i]+=dp[i-2];}}// 返回结果(将整个字符串解码,总方法数为dp[n])returndp[n];}}

空间优化版本

由于dp[i]只依赖dp[i-1]和dp[i-2]这两个值，我们可以不创建整个 dp 数组，而是用有两个变量动态滚动保存即可。

我们这里用prev1代表dp[i-1]，用prev2代表dp[i-2]，用cur代表dp[i]。

则状态转移方程为：cur = prev1 + prev2。

滚动的过程中，必须严格按照顺序：

1. prev2 = prev1
2. prev1 = cur

最终返回值是prev1，当整个字符串解码结束，prev1的值就是结果（若 n == 1，直接返回prev1，此时值为 1，结果也正确）

代码直接在优化初始化版改即可：

classSolution{publicintnumDecodings(Strings){// 预处理char[]ss=s.toCharArray();intn=ss.length;// 通过滚动数组优化空间复杂度:prev1为dp[i-1],prev2为dp[i-2]intprev1=ss[0]=='0'?0:1;intprev2=1;// 从左往右填dp表for(inti=2;i<=n;i++){intcur=0;// 先考虑ss[i]是否为0,若不为0就表示可以独自解码if(ss[i-1]!='0'){cur+=prev1;}// 再考虑ss[i]与ss[i-1]组合解码,判断组合后的字符是否满足条件inttemp=(ss[i-2]-'0')*10+ss[i-1]-'0';if(temp>=10&&temp<=26){cur+=prev2;}prev2=prev1;prev1=cur;}// 返回结果(将整个字符串解码,当滚动结束时总方法数为prev1)returnprev1;}}

---

完