一条包含字母A-Z 的消息通过以下映射进行了 编码 ：
'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"111" 可以将 "1" 中的每个 "1" 映射为 "A" ，从而得到 "AAA" ，或者可以将 "11" 和 "1"（分别为 "K" 和 "A" ）映射为 "KA" 。注意，"06" 不能映射为 "F" ，因为 "6" 和 "06" 不同。
给你一个只含数字的 非空 字符串 num ，请计算并返回 解码 方法的 总数 。题目数据保证答案肯定是一个 32 位 的整数。
原题链接：https://leetcode-cn.com/problems/decode-ways/
动态规划解法
确定状态
最后一步
由题可知，num是一个只含数字的非空字符串，解码规则比较简单，就是1 ~ 26分别映射为A ~ Z 26个字母，我们就知道，一个数字可以解码为一个字母，两个数字也可以解码为一个字母，
所以我们在考虑最后一步时，需要考虑到这两种情况。如下图所示：
如上图所示，num 为 1234523，如果最后一个解码单位为3，那么另一部分为 123452；如果最后一个解码单位为23，那么另一部分为12345。
确定子问题
确定完最后一步时，我们知道了最后一步解码单位有两种，将求解num解码方式转化为求解num-1 和num-2两个子问题，同时问题规模相应的变小了，如果剩余的部分可继续解码，那么还可以继续进行分解，直至不可分解为止。
转移方程
由上面的确定状态可以知，我们用f(x)代表从0~x位置字符串的解码方式数，可得转移方程为：
f(x) = f(x-1) + f(x-2)
注意上式成立是有条件的。
初始条件和边界情况
初始条件
如果输入的字符串为空串，那么解码只有只有一种方式，也解码为空串，即f(0) = 1;
边界情况
上面提到转移方程，如果当前字符串的最后两位可以进行解码，所以最后两位必须是10~26之间的某一个数，那么前面解码才会有效，即f(x) 需要加上f(x-2)；
同理如果当前字符串的最后一位可以进行解码，最后一位不能是0，那么前面解码才会有效，即f(x) 需要加上f(x-1)。
代码实现
public static int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int[] f = new int[s.length() + 1];
char[] chars = s.toCharArray();
f[0] = 1;
f[1] = chars[0] == '0' ? 0 : 1;
for (int i = 2; i <= s.length(); i++) {
// 如果要加上f[i - 2]，那么i位置的前两位必须是可解码的，即在10 ~ 26 之间 像01,03这种是无效的。
String is2 = String.valueOf(chars[i - 2]) + String.valueOf(chars[i - 1]);
int i2 = Integer.parseInt(is2);
if (i2 >= 10 && i2 <= 26) {
f[i] += f[i-2];
}
// 如果要加上f[i-1]，那么i位置的数字必须不能是0，否则无法继续解码
int i1 = Integer.parseInt(String.valueOf(chars[i - 1]));
if (i1 != 0) {
f[i] += f[i-1];
}
}
return f[s.length()];
}