POJ ACM习题【No.1163】

The Triangle

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 13904		Accepted: 7977

Description

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

(Figure 1)

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

Input

Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.

Output

Your program is to write to standard output. The highest sum is written as an integer.

Sample Input

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

Sample Output

30

 

此题解题的思路在于创建一个对应的三角结构，保存该层次的最大可能总和值。对于每一个值，需要按上一层左右两个值之中的较大者进行计算。

 

 

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int height = cin.nextInt();
		int[][] tree = new int[height][height]; 
		int[][] max = new int[height][height];
		int maxValue = 0;
		int left, right = 0;
		
		for(int i = 0; i < height; i++)
		{
			for(int j = 0; j <= i; j++)
			{
				tree[i][j] = cin.nextInt();
//				System.out.print(tree[i][j] + " ");
			}
//			System.out.println("\n");
		}
		
		max[0][0] = tree[0][0];
		

		
		for(int i = 1; i < height; i++)
		{
			for(int j = 0; j <= i; j++)
			{
				if(j == 0)
					max[i][j] = max[i-1][j] + tree[i][j];
				else if(j == i)
					max[i][j] = max[i-1][j-1] + tree[i][j];
				else
				{
					if(max[i-1][j-1] >= max[i-1][j])
						max[i][j] = max[i-1][j-1] + tree[i][j];
					else
						max[i][j] = max[i-1][j] + tree[i][j];
				}
			}
		}
		
		for(int j = 0; j < height; j++)
		{
			if(max[height-1][j] > maxValue)
				maxValue = max[height-1][j];
		}
		
		System.out.println(maxValue);
		

	}

}