傻逼题，做了好久。。
一开始backtrack,然后TLE。
只能动态规划。
dp[n]的话，如果s.charAt(n)不是0，那么dp[n] = dp[n-1];
然后如果s.charAt(n-1)s.charAt(n)组成的数是11-26 dp[n]+=dp[n-2]比较麻烦的地方
DP[1]的值，要想好了1还是2public int numDecodings(String s) { if(s.length() == 0) return 0; if(s.charAt(0) == '0') return 0; if(s.length() == 1) return 1; int[] dp = new int[s.length()]; dp[0] = 1; int temp = Integer.valueOf(s.substring(0,2)); if(temp == 10 || temp == 20) dp[1] = 1; else if(s.charAt(1) == '0' && temp > 20) return 0; else if(temp > 26) dp[1] = 1; else dp[1] = 2; System.out.println(dp[1]); for(int n = 2; n < s.length();n++) { if(s.charAt(n) != '0') dp[n] += dp[n-1]; if(s.charAt(n-1) == '1' || (s.charAt(n-1) == '2' && s.charAt(n) <= '6')) dp[n] += dp[n-2]; } return dp[dp.length-1]; } 这个傻逼题18%的通过率是有原因的。
---
二刷。
DP[0]DP[1]几乎花了2/3的时间来考虑各种CASE，还是没考虑全，这个题思路不难，但是做对很难。。。
dp[i] 就是 0-i的所有可能性。
对于s.charAt(i)来说：
要么他自己作为一个数字，可以是1-9，此时dp[i]和dp[i-1]一样。是0的话就不行。。 要么他和前一位组成两位数，10-26，此时dp[i] 和 dp[i-2]一样，因为他把s.charAt(i-1)抢走了和自己抱团取暖了。所以最终dp[i]的可能性就是上面所属的2种情况相加。
不会出现，一个数既要和前面组成，又要和后面组成。
继续刚才的步骤，用dp[i+1]来说，假如i+1要拿走i来和自己抱团取暖，那dp[i+1]是要加上dp[i-1]，而dp[i-1]的所有可能性中，没有i和i-1抱团取暖的组合所以不影响..这东西理解起来比叙述起来容易些。
然后最讨厌的是前两位数字，分成好几种可能：
首位是0，不行。 组成10或者20，dp[1] = 1。 30,40,50，60,70,80,90，也不行。。 11-19,21-26，dp[1] = 2。 其余，dp[1] = 1不太容易想全，基本是提交之后才能发现错误。。
public class Solution { public int numDecodings(String s) { if(s.length() == 0) return 0; if(s.charAt(0) == '0') return 0; if(s.length() == 1) return 1; int[] dp = new int[s.length()]; dp[0] = 1; int temp = Integer.valueOf(s.substring(0,2)); if(s.charAt(1) == '0') { if(temp == 10 || temp == 20) dp[1] = 1; else return 0; } else if(temp <= 26) dp[1] = 2; else dp[1] = 1; for(int i = 2; i < s.length(); i++) { char tempC = s.charAt(i); char prevC = s.charAt(i-1); dp[i] = tempC == '0'? 0:dp[i-1]; if(prevC != '0' && Integer.valueOf(s.substring(i-1,i+1)) <= 26) { dp[i] += dp[i-2]; } } return dp[dp.length-1]; }} ----
三刷。
印象中DP[1]判断比较麻烦，结果三刷还是栽了，我真是个傻逼。
拿dp[i]来说，他自己如果是1-9，那么首先在i-1的基础上，他可以独立使得解析完整，首先有i-1种解；接下来看他和前面以为能不能组成26以内的数，能的话，说明他可以和前一位组成一个两位数，我们又多了一种解析方式，与i-2相等。两种情况相加就行。
Time: O(n)
Space: O(n)public class Solution { public int numDecodings(String s) { if (s.length() == 0) return s.length(); if (s.charAt(0) == '0') return 0; if (s.length() == 1) return s.length(); int[] dp = new int[s.length() + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i < dp.length; i++) { int a = Integer.valueOf(s.substring(i-1, i)); int b = Integer.valueOf(s.substring(i-2,i)); if (b >= 10 && b <= 26) dp[i] += dp[i-2]; if (a >= 1 && a <= 9) dp[i] += dp[i-1]; } return dp[s.length()]; }}