thetriangle.java

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

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


/**
 * ID:1163，3176
 * 动态规划
 * @author yhm
 *
 */
public class TheTriangle {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int size = cin.nextInt();
		int[][] triangle = new int[size+1][size+1]; 
		for(int i=1;i<=size;i++){
			for(int j=1;j<=i;j++){
				triangle[i][j] = cin.nextInt();
			}
		}
		int r = solve(triangle,size);
		System.out.println(r);

	}
	
	static int solve(int[][] triangle, int size){
		int[][] cost = new int[size+1][size+1];
		int maxOfLeaf=-1;
		for(int i=1;i<=size;i++){
			for(int j=1;j<=i;j++){
				int temp1 = cost[i-1][j];
				int temp2 = cost[i-1][j-1];
				int max = Math.max(temp1, temp2);
				cost[i][j] = max+triangle[i][j];
				if(i==size){
					if(cost[i][j]>=maxOfLeaf){
						maxOfLeaf = cost[i][j];
					}
				}
			}
		}
		return maxOfLeaf;
	}

}