暴力递归转动态规划（四）

题目
规定1对应A、2对应B、3对应C…26对应Z，那么一个数字字符串比如"111"，就可以转化为：“AAA”、“KA"或"AK”，给定一个数字字符组成的字符串str，返回有多少种转化结果。

解释一下，字符串"111"，可以拆分成"1"-“1”-“1"或者字符串"11”-“1"或者字符串"1”-“11”，所以有3种转化结果。

暴力递归
依然首先是暴力递归的思路，将str转换成char[]，共有两种转换方式。

1. 自己单独转换，不过有一点注意，如果我当前字符是’0’的时候是不支持转化的，因为没有对应字母支撑。
2. 两个字符拼接后转换，同样也有一点主要注意，因为是只有26个英文字母， 所以两个字符拼接后，不能以’0’字符开头，并且相加后 < 27。

代码
代码中index == chars.length时 return 1 是当 char[] 走完，下面没字符之后，返回的1代表是一种转换结果，对当前转换结果的承认，如果转换不成功，中间过程中有0 或者 拼接完之后是 "01"或者拼接玩之后"28"这种没有字母对应的字符，直接就会在过程中进行 return 0

 public static int number(String str){if (str == null || str.length() == 0){return 0;}char[] chars = str.toCharArray();//process()方法返回方法返回字符串转化结果return process(chars,0);}//从index位置开始转化，index之前的不在意public static int process(char[] chars,int index){//如果走到了chars.length的位置，说明走完了，if (index == chars.length){return 1;}//如果当前字符是'0'，直接return 不往下走了。if (chars[index] == '0'){return 0;}//单独自己转换int ans = process(chars,index +1);//拼接后面的转化，先判断当前是不是最后一个字符，并且满足转化条件if (index + 1 < chars.length &&(( chars[index] - '0') * 10 + (chars[index + 1] - '0') ) < 27){ans += process(chars,index +2);}return ans;}

动态规划
根据可变参数index改动态规划，因为只有一个可变参数，所以是一个一维数组，调用过程process是index + 1 和 index + 2，所以是依赖后面，根据暴力递归代码中base case index == chars.length return 1，可确定数组最后一个位置的值，由后向前推导。

dp表组成根据暴力递归代码进行修改即可。

public static int dp(String str) {if (str == null || str.length() == 0) {return 0;}char[] strs = str.toCharArray();int N = strs.length;int[] dp = new int[N + 1];dp[N] = 1;for (int i = N - 1; i >= 0; i--) {if (strs[i] != '0'){int ans =  dp[i + 1];if (i + 1 < N && (dp[i] - '0') * 10 + (dp[i + 1] - '0') < 27) {ans += dp[i + 2];}dp[i] = ans;}}return dp[0];}