Example 1: Number Triangle

As shown below, there is a number triangle. Write a program to compute a path from the top to the bottom such that the sum of the numbers along the path is maximized. Only the maximum sum needs to be output.

Requirements:

1. At each step, you may move down along the left diagonal or the right diagonal.
2. The number of rows in the triangle is less than or equal to 100.
3. The numbers in the triangle are 0, 1, …, 99.

The test data is entered line by line from the keyboard. For the example shown above, the input format should be as follows:

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

Algorithm Analysis

There are multiple ways to solve this problem. From the perspective of dynamic programming, consider the following idea:

When moving from the top along a certain path and reaching level i, then proceeding to level i + 1, the choice must be to move toward the larger of the two possible downward paths. Therefore, we can adopt a bottom-up approach.

Let a[i][j] denote the maximum sum obtainable starting from position (i, j) and reaching the bottom level n. Then:

a[i][j] = max(a[i][j] + a[i+1][j], a[i][j] + a[i+1][j+1])

The value a[1][1] is the required maximum total sum.