brackets.java

PKU中一些数据结构基本算法题的java实现

package PKU.DP;
import java.util.Scanner;


/**
 * ID:2955
 * DP
 * @author yhm
 *
 */
public class Brackets {

	static int brackets=0;
	static int parentheses=1;
	static int len=2;
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			String str = cin.next();
			if(str.equals("end")){
				break;
			}
			
			solve(str);
			
		}

	}
	
	static void solve(String str){
		int length = str.length();
		int[][] dp = new int[length][length];
		for(int i=0;i<length;i++){
			dp[i][i] = 1;
		}
		
		for(int i=length-2;i>=0;i--){
			for(int j=i+1;j<length;j++){
				int min = Integer.MAX_VALUE;
				if((str.charAt(i)=='(' && str.charAt(j)==')') || (str.charAt(i)=='[' && str.charAt(j)==']')){
					min = Math.min(min, dp[i+1][j-1]);
				}
				if(str.charAt(i)=='(' || str.charAt(i)=='['){
					min = Math.min(min, dp[i+1][j]+1);
				}
				if(str.charAt(j)==')' || str.charAt(j)==']'){
					min = Math.min(min, dp[i][j-1]+1);
				}
				for(int k=i;k<j;k++){
					min = Math.min(min, dp[i][k]+dp[k+1][j]);
				}
				dp[i][j]=min;
			}
		}
		
		System.out.println(length-dp[0][length-1]);
		

	}

}