动态规划 --- Leedcode 91 解码方法 （medium）

题目

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

'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

解析

这道题很像leedcode 70爬楼梯的问题，爬楼梯问题，一次只能爬一层或者爬两层；这个解码问题也是一次分解一个字符，或者一次分解两个字符，而不同的是，难度增加了，我们要判断每次分割的字符是否小于26,并且分割的字符第一个是’0’也不满足。

看一个例子：

• 12的解码数 = 2
  1 - 2
  12
• 1的解码数 = 1
  1
• 122的解码数 = 12的解码数 + 1 的解码数
  1 - 2 - 2
  12 - 2
  1 - 22
  122的解码数如何判断：看增加的这位是否可以独立成一位(即不是’0’就可以) 或者是否可以与前面的一位合并（即合并之后小于等于26）

转为动态规划：

• 122的动态规划方程： dp[3] = dp[2] + dp[1]
• dp[2]为12的解码数；dp[1]为1的解码数

代码：

 public static int numDecodings(String s) {
	        if(s.charAt(0) == '0') {
	        	return 0;
	        }
	        int []dp = new int[s.length()+1]; // 存储相应字符长度的解码数
	        
	       dp[0] = dp[1] = 1;
	        
	        for(int i = 2; i<= s.length();i++) {
	        // 判断该位位是否能独立  
	        	if(s.charAt(i-1) != '0') {
	        		dp[i] += dp[i-1];
	        	}
	      // 判断该位于前一位数是否合法（即是否小于等于26）
	        	if(s.charAt(i-2) == '1' || (s.charAt(i-2) == '2' &&s.charAt(i-1) <= '6')) {
		        	dp[i] += dp[i-2];
		        }	 
	        }
	        return dp[s.length()];
	    }
	    

注意：将dp[0]也设为1，是为了解决最前面的两个字符合并在一起的情况。
如果最前面的两个字符合并小于等于26，则dp[2]的解码方法就为1。