[数据结构与算法]动态规划练习——规定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));
	}
}