动态规划-91. 解码方法
点击蓝字关注我，一起成长
题目
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
2
样例
示例1：
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例2：
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
3
样例解读
由题目可以确定：
一定要考虑 0 的情况
类似于：01， 00 等0开头的两位数是不可能的。
读过题目之后，相信大家都意识到需要向前比较，即是当前数能不能够跟上一个数进行组合，并且顺利解码出来。
4
解答与代码
由上分析可以得到：
动态思想：
由题目可以知道，假设我们已经知道了整个数字串前 i - 1 个数字组合的解码数，记为 dp[i - 1] 。
当我们求前 i 个数字的组合的时候，我们有两种组合：
（1）第 i 个数字自己作为一个字母进行解码。
（2）第 i 个数字与前一个数字 i - 1 组合作为一个字母进行解码。此时的隐含条件就是：这两个数字的组合的范围必须为 10 - 26。
所以，可以得到规律：
（1）当s[i] == 0 .则s[i - 1] == '1' or '2'时，即是组合是10 or 20 ，则dp[i] = dp[ i -2], 否则返回0（即是00， 30 - 90）
（2）当s[i - 1] 和 s[i] 的组合是 11 - 26，则能够组合一起，也能分开。得到dp[i] = dp[i - 1] + dp[i - 2]；
（3）当s[i - 1] 和 s[i] 的组合是 27以上的时候，则两者不能组合一起，所以dp[i] = dp[i - 1];
答案：
class Solution {public int numDecodings(String s) {// dp[i] = dp[i - 1] +dp[i - 2]//向前比较：//（1）当s[i] == 0 .则s[i - 1] == '1' or '2'时，即是组合是10 or 20 ，则dp[i] = dp[ i -2], 否则返回0（即是00， 30 - 90）//（2）当s[i - 1] 和 s[i] 的组合是 11 - 26，则能够组合一起，也能分开。得到dp[i] = dp[i - 1] + dp[i - 2]//(3)当s[i - 1] 和 s[i] 的组合是 27以上的时候，则两者不能组合一起，所以dp[i] = dp[i - 1];if(s == null || s.length() == 0 ||s.charAt(0) == '0'){return 0;}char[] ch = s.toCharArray();final int size = s.length();int[] dp = new int[size];if(size == 1) return 1;dp[0] = 1;if(ch[1] == '0'){if(ch[0] == '1' || ch[0] == '2'){dp[1] = 1; // 10 ,20}else{dp[1] = 0; // 不符合逻辑}}else if(ch[0] == '1' || (ch[0] == '2' && ch[1] >= '0' && ch[1] <= '6')){dp[1] = 2;}else{dp[1] = 1;}for(int i = 2 ; i < size ;i++){if(ch[i] == '0'){if(ch[i - 1] == '1' || ch[i - 1] == '2'){dp[i] = dp[i - 2];//10, 20即是最后两个要组合在一起}else{return 0; // 不符合逻辑}}else if(ch[i - 1] == '1' || (ch[i - 1] == '2' && ch[i] >= '0' && ch[i] <= '6')){dp[i] = dp[i - 1] + dp[i - 2]; //涵盖了11 - 26}else {dp[i] = dp[i -1]; //27以上的。就不能组合了,所以只有分开的一种情况}}return dp[size - 1];}}
5
预告
本次专题：动态规划算法
明天预告题目：
Leetcode -96. 不同的二叉搜索树
● 扫码关注我
题目素材来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways/
喜欢我们的内容就点“在看”分享给小伙伴哦