A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Dp。
定义： s.(0, ~n) 一共有几种情况
转移方程：f[n] = f[n - 1](条件s[n] != 0) + f[n-2](条件s[n-1]s[n]组成的数字在[10, 26]之间)
细节：
1.因为依赖前两个状态，所以数组开的是[s.length() + 2]。初始化[0] = 0, [1] = 1，为了让第一个字符往前拼两位数无效，第二个字符往前拼两位数有效。
2.为了让第一个字符能往前拼成两位数，需要一开始对s做s = “0” + s; 处理
3. String -> int用Integer.parseInt(), int -> String用String.valueOf() / (Integer) i.toString()。要得到什么类型就用什么类型的库；int->String是一选一的关系所以方法名比较专一，而String->int是多选一的关系（String可以转成很多其他类型）所以方法名比较general。
4.这题小心0, 01, 10的case，但按上面的转移方程走就没问题。01, 02这些都不算有效的解码方式。0: 0种，10: 1种，101: 1种。
5.不用单独处理说30这种两边都不对的情况直接返回0，你两次都没有+=的话自动就0了，以后所有产生的数字也会是0，这种case自包含的。
实现：
class Solution { // P1: 要处理数字是0的情况 public int numDecodings(String s) { if (s == null || s.length() == 0) { return 0; } int[] dp = new int[s.length() + 2]; dp[0] = 0; dp[1] = 1; s = "0" + s; for (int i = 2; i < dp.length; i++) { int oneDigit = Integer.parseInt(s.substring(i - 1, i)); int twoDigit = Integer.parseInt(s.substring(i - 2, i)); if (oneDigit != 0) { dp[i] += dp[i - 1]; } if (twoDigit >= 10 && twoDigit <= 26) { dp[i] += dp[i - 2]; } } return dp[dp.length - 1]; } }