一条包含字母 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) 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways
思路：
第一个元素如果是1，那么就一种可能
如果加进来了一个2，那么两种 1 - 2或者12
如果再加进来一个2，那么三种1 - 2 - 2 或者12 - 2或者一个新的1 - 22
如果再加进来一个2，那么五种1 - 2 - 2 - 2或者12 - 2 - 2或者1 - 22 -2 或者两个新的1 - 2 - 22和12 - 22
现在就可以看出来了，是一个DP的算法题，加进来的数可能是可以直接贴上去的，可能是要单独的，也可能是没有用的
看到评论里有个说，想个逻辑5分钟，划分边界2小时，评论夸张了点，但是也到位
这题如果没有边界的话，其实就是一个很简单的DP问题
class Solution { public int numDecodings(String s) { char[] arr = s.toCharArray(); int[] dp = new int[s.length()+1]; dp[0] = 1; dp[1] = arr[0]=='0'?0:1; if(s.length()<=1) return dp[1]; for(int i=2;i<=s.length();i++){ int n = (arr[i-2]-'0')*10+(arr[i-1]-'0'); //如果最后一位=='0'，且新加入的=='0'，无法解码，返回0； if(arr[i-1]=='0' && arr[i-2]=='0'){ return 0; } //如果只有最后一位=='0'，则新加入的只能单独放在最后，不能与最后一位合并(不能以0开头) else if(arr[i-2]=='0'){ dp[i] = dp[i-1]; } //如果只有新加入的=='0'，则新加入的不能单独放置，必须与最后一位合并，并且如果合并结果大于26，返回0，否则 else if(arr[i-1]=='0'){ if(n>26) return 0; dp[i] = dp[i-2]; } //如果 合并<=26: 则新加入可以“单独”放在每个解码结果之后后，并且如果以最后一位单独结尾，此时可以合并 else if(n>26){ dp[i] = dp[i-1]; } //如果 合并>26: 此时最后一位又不能与新加入的合并，新加入的只能单独放在dp[i]的每一种情况的最后 else{ dp[i] = dp[i-1]+dp[i-2]; } } return dp[dp.length-1]; } }