littleshopofflowers.java

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

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


/**
 * ID:1157
 * 动态规划，result[i][j]是包含该处的当前最大值
 * @author yhm
 *
 */
public class LittleShopOfFlowers {

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

	}
	
	static int solve(int[][] f, int row, int col){
		int[][] result = new int[row][col];
		for(int i=0;i<row;i++){
			Arrays.fill(result[i],Integer.MIN_VALUE);
		}		
		for(int j=0;j<col;j++){
			result[0][j] = f[0][j];
		}
		int max = Integer.MIN_VALUE;
		for(int i=1;i<row;i++){
			for(int j=i;j<col;j++){
				result[i][j] = f[i][j] + findMax(result[i-1], j-1);
				if(i==row-1){
					max = Math.max(max, result[i][j]);
				}
			}
		}
		return max;
	}
	
	static int findMax(int[] a, int n){
		int max = Integer.MIN_VALUE;
		for(int i=0;i<=n;i++){
			max = Math.max(max, a[i]);
		}
		return max;
	}

}