A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
题意：如果从A到Z可以按1-26进行编码，那么给出一串数字，有多少种解码方式？
思路：
例如给出1221，如果从头开始用深度搜索的方式找，对于每一位，都有可能有两种解码方法，时间复杂度将会非常高。
换一种角度，对于以每一位结尾的字符串来说，它的解码方法和前面数字串解码的方式相关，有点像jump那道题，可以用动态规划的方法解决。
以dp[n]表示从头到第n-1位有多少种解码方法，如果当前位置n的数字是1-9，那么dp[n] += dp[n-1]，如果n-1位不等于0并且和n位组合起来的数字小于等于26，dp[n] += dp[n-2]。dp[0]需要初始化为1，因为计算dp[2]时，如果前两位组合是一个合法的编码，将需要dp[0]。
public int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int len = s.length();
int[] dp = new int[len + 1];
dp[0] = 1;
dp[1] = s.charAt(0) != '0' ? 1 : 0;
for (int i = 2; i <= len; i++) {
if (s.charAt(i-1) != '0') {
dp[i] += dp[i-1];
}
if (s.charAt(i-2) != '0' && Integer.valueOf(s.substring(i-2, i)) <= 26) {
dp[i] += dp[i-2];
}
}
return dp[len];
}