题目
规定1和A对应、2和B对应、3和C对应…那么一个数字字符串比如"111”就可以转化为：'AAA"、 “KA"和"AK”。给定一个只有数字字符组成的字符串str，返回有多少种转化结果
动态规划关键在于暴力解是否能够顺利写出来，也就是说把尝试过程想清楚后，再将其替换成结构化的缓存结构，所以尝试过程很重要。这个题的暴力解请看这篇博客——暴力递归——从左往右的尝试模型1，Facebook面试真题，。博主多次讲到过，改动态规划的过程跟原题意已经没有关系了，也就是说跟原题意已经解耦了。
所以，如果你看懂了暴力尝试的方法后，我们就直接在此基础上改动态规划：
[code]public static int dpways1(String s) { if(s==null || s.length()==0) { return 0; } char[] str=s.toCharArray(); int N=str.length; int[] dp=new int[N+1]; dp[N]=1; for(int i=N-1; i>=0; i--) { if(str=='0') { dp=0; }else if(str=='1') { dp=dp[i+1]; if(i+1 |
