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

文章目录题目解析算法原理确定状态表示确定状态转移方程初始化确定填表顺序确定返回值细节问题代码实现普通动态规划优化初始化版本空间优化版本题目链接91. 解码方法题目解析动态规划Dynamic programming简称 DP是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题它们的结果都逐渐被计算并被保存从简单的问题直到整个问题都被解决。因此动态规划保存递归时的结果因而不会在解决同样的问题时花费不必要的时间。通常的解决步骤有五步确定状态表示/dp表的含义确定状态转移方程/递推公式初始化确定填表顺序确定返回值一条包含字母A-Z的消息通过以下映射进行了编码1 - A2 - B...25 - Y26 - 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]解码的思路若s[i]可以单独解码则有1 s[i] 9此时解码方法数和前一个字符的解码方法数一样即dp[i] dp[i - 1]若s[i]与前一个字符s[i-1]合并解码则当满足条件10 b*10 a 26(其中 b 为 s[i-1] 的 ASCII 码转为整数类型的值a 同理) 时此时由于和前一个字符组合了解码方法数就与前两个字符的解码方法一样即dp[i] dp[i-2]综合以上两种情况可以得出状态转移方程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[]sss.toCharArray();intnss.length;// 创建dp表(dp[i]表示到位置i时的解码方法数)int[]dpnewint[n];// 初始化第一个字符(若为0——即有前导零,解码方法数是0)dp[0]ss[0]0?0:1;// 边界情况(消息长度只有1)if(n1){returndp[0];}// 初始化第二个字符// 考虑第一种情况:独自解码(必须满足1ch9);同时也必须保证ss[0]非0if(ss[0]!0ss[1]!0){dp[1]1;}// 考虑第二种情况:和前一个字符组合解码(组合后的字符必须满足10char26)inttemp(ss[0]-0)*10ss[1]-0;if(temp10temp26){dp[1]1;}// 从左往右填dp表for(inti2;in;i){// 先考虑ss[i]是否为0,若不为0就表示可以独自解码if(ss[i]!0){dp[i]dp[i-1];}// 再考虑ss[i]与ss[i-1]组合解码,判断组合后的字符是否满足条件temp(ss[i-1]-0)*10ss[i]-0;if(temp10temp26){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[]sss.toCharArray();intnss.length;// 创建dp表(dp[i]表示到位置i时的解码方法数),往右移动一个单位int[]dpnewint[n1];// 初始化第一个位置的值为1dp[0]1;// 初始化第一个字符(若为0——即有前导零,解码方法数是0)dp[1]ss[0]0?0:1;// 从左往右填dp表for(inti2;in;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)*10ss[i-1]-0;if(temp10temp26){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。滚动的过程中必须严格按照顺序prev2 prev1prev1 cur最终返回值是prev1当整个字符串解码结束prev1的值就是结果若 n 1直接返回prev1此时值为 1结果也正确代码直接在优化初始化版改即可classSolution{publicintnumDecodings(Strings){// 预处理char[]sss.toCharArray();intnss.length;// 通过滚动数组优化空间复杂度:prev1为dp[i-1],prev2为dp[i-2]intprev1ss[0]0?0:1;intprev21;// 从左往右填dp表for(inti2;in;i){intcur0;// 先考虑ss[i]是否为0,若不为0就表示可以独自解码if(ss[i-1]!0){curprev1;}// 再考虑ss[i]与ss[i-1]组合解码,判断组合后的字符是否满足条件inttemp(ss[i-2]-0)*10ss[i-1]-0;if(temp10temp26){curprev2;}prev2prev1;prev1cur;}// 返回结果(将整个字符串解码,当滚动结束时总方法数为prev1)returnprev1;}}完