动态规划练习——规定1和A对应、2和B对应、3和C对应…那么一个数字字符串比如“111”就可以转化为：‘AAA“、 “KA“和“AK”。给定一个只有数字字符组成的字符串str，返回有多少种转化结果

题目

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

动态规划关键在于暴力解是否能够顺利写出来，也就是说把尝试过程想清楚后，再将其替换成结构化的缓存结构，所以尝试过程很重要。这个题的暴力解请看这篇博客——暴力递归——从左往右的尝试模型1，Facebook面试真题，。博主多次讲到过，改动态规划的过程跟原题意已经没有关系了，也就是说跟原题意已经解耦了。

所以，如果你看懂了暴力尝试的方法后，我们就直接在此基础上改动态规划：

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[i]=='0') {
                dp[i]=0;
            }else if(str[i]=='1') {
                dp[i]=dp[i+1];
                if(i+1<N) {
                    dp[i]+=dp[i+2];
                }
            }else if(str[i]=='2') {
                dp[i]=dp[i+1];
                if(i+1<N && (str[i+1]>='0' && str[i+1]<='6')) {
                    dp[i]+=dp[i+2];
                }
            }else {
                dp[i]=dp[i+1];
            }
        }
        return dp[0];
    }

至于如果你要问为什么要这么改的话，那就将两种方法对比一看就知道啦！其实没有为什么，就是照着暴力尝试的过程无脑改就行。

完整代码：

package com.harrison.class13;

public class Code04_ConvertToString {
    public static int process1(char[] str,int i) {
        if(i==str.length) {
            return 1;
        }
        if(str[i]=='0') {
            return 0;
        }
        if(str[i]=='1') {
            int res=process1(str, i+1);
            if(i+1<str.length) {
                res+=process1(str, i+2);
            }
            return res;
        }
        if(str[i]=='2') {
            int res=process1(str, i+1);
            if(i+1<str.length && (str[i+1]>='0' && str[i+1]<='6')) {
                res+=process1(str, i+2);
            }
            return res;
        }
        return process1(str, i+1);
    }
    
    public static int convert1(String s) {
        if(s==null || s.length()==0) {
            return 0;
        }
        char[] str=s.toCharArray();
        return process1(str, 0);
    }
    
    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[i]=='0') {
                dp[i]=0;
            }else if(str[i]=='1') {
                dp[i]=dp[i+1];
                if(i+1<N) {
                    dp[i]+=dp[i+2];
                }
            }else if(str[i]=='2') {
                dp[i]=dp[i+1];
                if(i+1<N && (str[i+1]>='0' && str[i+1]<='6')) {
                    dp[i]+=dp[i+2];
                }
            }else {
                dp[i]=dp[i+1];
            }
        }
        return dp[0];
    }
    
    public static void main(String[] args) {
        String test="11111";
        System.out.println(convert1(test));
        System.out.println(dpways1(test));
    }
}