POJ1163

Description

7
3   8
8   1   0
2   7   4   4
4   5   2   6   5

(Figure 1)

Input

Output

Sample Input

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

Sample Output

30

import java.util.Scanner;

public class Poj1163 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int rows = sc.nextInt();

		int[][] a = new int[rows][rows];

		// 录入数据
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j <= i; j++) {
				a[i][j] = sc.nextInt();
			}
		}

		// 动态规划，获取最大值
		for (int i = rows - 2; i >= 0; i--) {
			for (int j = 0; j <= i; j++) {
				a[i][j] = Math.max(a[i + 1][j], a[i + 1][j + 1]) + a[i][j];
			}
		}

		System.out.println(a[0][0]);
	}

}

POJ1163

原文：http://blog.csdn.net/bear_huangzhen/article/details/45967189