来源:《算法与数据结构最优解》左程云著 --hihoCoder练习题
问题描述：给定一个字符串str，str全部由数字字符组成，如果str中某一个或者某相邻两个字符组成的子串在1~26之间，则这个子串可以转换为一个字母。规定“1”转换为“A”，“2”转换为“B”……“26”转换为“Z”。求str有多少种不同的转换结果。
输入
字符串str(|str|<20)
输出
可转换结果的数目
样例输入
12345678
样例输出
3
思路：动态规划，其实就是举个简单的样例逐步推导出递归式，下面详细的分析一下
dp一维数组存储对应长度字符能解释的数目
动态规划: 举例123 应有 ABC LC AW(123 *12 3* *1 23* )3种情况
初始化dp[0] = 1, dp[1] = 2
当考虑第n(该例子中为3)个字符时,因为3在1-9字符之间,
即包含n-1长度(例子中12)能解释的字符串数目 即dp[2] += dp[1]
又因为23可以单独解释一个字母,所以还包含n-2长度的字符串,
即dp[2] += dp[0];dp[2] = 3,
更简单的说可以看做新加入的字符与
前一个字符可以组合新的字符,与前n-2个字符看成新整体,
还可以独立成一个个体与前n-1个字符看成一个新整体，
因此在特定的条件下可得递归式: dp[n] = dp[n-1]+dp[n-2]
特别的第一个元素为字符0时，return 0;长度大于等于二时dp[1]在特别情况下赋值为
（详见代码处理）
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
int res = numDec(s);
System.out.println(res);
}
private static int numDec(String s) {
if(s == null||s.length() == 0||s.charAt(0) == '0')
return 0;
if(s.length() == 1) {
if(s.charAt(0) != '0')
return 1;
else
return 0;
}
char[] arr = s.toCharArray();
int[] dp = new int[s.length()];
//初始条件
dp[0] = 1;
if(arr[1] != '0'&&((cInt(arr[0])*10
+ cInt(arr[1])) <= 26))
dp[1] = 2;
else
dp[1] = 1;
for(int i = 2; i < s.length(); i++) {
if(arr[i] != '0')
dp[i] += dp[i-1];
if(arr[i-1] != '0'&&((cInt(arr[i-1])*10
+ cInt(arr[i])) <= 26))
dp[i] += dp[i-2];
}
return dp[s.length() - 1];
}
private static int cInt(char c) {
return c - '0';
}
}
