一条包含字母 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) 。
/* 此题和爬楼梯是同一个类型的问题，难点在于其添加了许多限制条件，只要避开限制条件就可以完美解题了 每次递进，可以选取一个数也可以选取两个数： s[i] != '0' 如果 s[i-1]s[i] <= 26, 则 dp[i] = dp[i-1] + dp[i-2] 如果 s[i-1]s[i] > 26, 则 dp[i] = dp[i-1], 这是因为 s[i-1]s[i] 组成的两位数无法翻译 s[i] == '0' 如果 s[i-1]s[i] <= 26, 则 dp[i] = dp[i-2], 这是因为 s[i] 无法翻译 还有一些情景直接使得整个序列无法被翻译： 相邻的两个 ‘0’ 以 ‘0’ 结尾的大于 26 的数字 作者：nfgc 链接：https://leetcode-cn.com/problems/decode-ways/solution/dong-tai-gui-hua-tu-jie-by-nfgc/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 */ class Solution { public int numDecodings(String s) { if(s.charAt(0)=='0') return 0; int length=s.length(); int[] dp=new int[length+1]; dp[0]=1; dp[1]=1; for(int i=2;i<=length;i++){ int temp=inRange(s.charAt(i-2),s.charAt(i-1)); if(temp==2){ dp[i]=dp[i-1]+dp[i-2]; }else if(temp==1){ dp[i]=dp[i-1]; }else if(temp==3){ dp[i]=dp[i-2]; }else{ return 0; } } return dp[length]; } public int inRange(char c1,char c2){ if((c1=='0'&&c2=='0')||(c2=='0'&&c1>'2')){ return 0; }else if(c2=='0'&&c1<='2'){ return 3; }else if(c1>'2'||c1=='0'||c2=='0'||(c1=='2'&&c2>'6')){ return 1; } return 2; } }