动态规划总结

• 1、动态规划试题
• • 2、返回最长的回文字符串

给定两个字符串str1和str2，
返回这两个字符串的最长公共子序列长度
比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k”
最长公共子序列是“123456”，所以返回长度6

public static int maxCommonQueue(String s1,String s2){
	if(s1==null || s2==null || s1.length==0 || s2.length==0){
		return 0;
	}
	char str1=s1.toCharArray();
	char str2=s2.toCharArray();
	return process(str1,str2,str1.length-1,str2.length-1);
}
public static int process(char[] str1,char[] str2 ,int len1,int len2){
	if(len1==0 && len2==0){
	return str1[0]==str2[0]?1:0
	}else if(len1==0){
		if(str1[0] == str2[0]){
			return 1;
		}else{
			return process(str1,str2,len1,len2-1);
		}
	}else if(len2==0){
		if(str2[0]==str1[len1]){
			return 1;
		}else{
			return process(str1,str2,len1-1,len2);
		}
	}else{
		int p1=process(str1,str2,len1-1,len2);
		int p2=process(str1,str2,len1,len2-1);
		int p3=str1[len1]==str2[len2]?(1+process(str1,str2,len1-1,len2-1)):0;
		return Math.max(p1,Math.max(p2,p3));
	}
}

优化算法：

public static int dp(String s1,String s2){
	if(s1==null || s2==null || s1.length==0 || s2.length==0){
		return 0;
	}
	int len1=s1.length;
	int len2=s2.length;
	char[] str1=s1.toCharArray();
	char[] str2=s2.toCharArray();
	int[][] dp=new int[len1+1][len2+1];
	dp[0][0]=str1[0]==str2[0]?1:0;
	for(int i=1;i
		dp[i][0]=str[len2]==str1[0]?1:dp[len1-1][0];	
	}
	for(int j=1;j
		dp[0][j]=str1[len1]==str2[0]?1:dp[0][len2-1]
	}
	for(int i=1;i
		for(int j=1;j
			int p1=dp[i-1][j];
			int p2=dp[i][j-1];
			int p2=str1[i]==str2[j]?(1+dp[i-1][j-1]):0;
			dp[i][j]=Math.max(p1,Math.max(p2,p3));
		}
	}
	return dp[len1-1][len2-1];
}

给定一个字符串str，返回这个字符串的最长回文子序列长度
比如 ： str = “a12b3c43def2ghi1kpm”
最长回文子序列是“1234321”或者“123c321”，返回长度7

public static int maxLength(String s){
	if(s==null || s.length()=0){
		return 0;
	}
	char[] str=s.toCharArray();
	return process(str,0,str.length-1);
}
public static int process(char[] str,int L,int R){
	if(L==R){
		return 1;
	}
	if(L==R-1){
		return str[L]==str[R-1]?2:1;
	}
	int p1=process(str,L+1,R-1);
	int p2=process(str,L+1,R);
	int p3=process(str,L,R-1);
	int p4=str[L]==str[R]?(2+process(L+1,R-1)):0;
	return Math.max(Math.max(p1,p2),Math.max(p3,p4));
}

优化：

public static int maxLength(String s){
	if(s==null || s.length()==0){
		return 0;
	}
	char[] str=s.toCharArray();
	int N=str.length;
	int[][] dp=new int[N][N];
	dp[N-1][N-1]=1;
	for(int i=0;i
		dp[i][i]=1;
		dp[i][i+1]=str[i]==str[i+1]?2:1;
	}
	for(int i=N-3;i>=0;i--){
		for(int j=i+2;i
			int p1=dp[i+1][j-1];
			int p2=dp[i+1][j];
			int p3=dp[i][j-1];
			int p4=str[i]==str[j]?(2+dp[i+1][j-1]):0;
			dp[i][j]=Math.max(Math.max(p1,p2),Math.max(p3,p4));
		}
	}
	return dp[0][N-1]
}