triangle Class Reference

List of all members.

Public Member Functions
void	push (unsigned short k)
void	label_row (unsigned short n)
unsigned	maxN ()
void	push (unsigned short k)
void	label_row (unsigned short n)
unsigned	maxN ()

---

Detailed Description

Apply the concept of dynamic programming The problem is divided into several stages, in which there are a number of states. Decision is made in each stage, and is passed to next stage. The problem is solved in the last stage.

Dynamic programming eventually generates a recursion, either forward or backward.

Forward recursion, e.g.

3
7 5
2 4 6
8 5 9 3
max sum = 3 + 7 + 4 + 9 = 23

When there is only one row, 3
Then the answer is 3 of course.

When there are two rows, label each number with the cumulated sums from 1st row to 2nd row:

3[3] 7[10] 5[8]

Since 10 is the max of all numbers in the bottom row, 10 is the max sum.

Therefore the problem is equivalent to finding the max cumulated sum in the bottom row.

When there are more rows, we can split the problem into several sub-problems: Given the number of rows n.

• 1) Label all the numbers in the (n - 1)-th row.
• 2) For each labeled numbers in the (n – 1)-th row, evaluate the cumulated sum S of the adjacent numbers in the n-th row.
• 3) Find the max sum in the n-th row.

Note: There are two possible cases in step 2:

• The number in n-th row is not yet labeled; then label it with S.
• The number is already labeled with S0; then re-label it with value of min(S0, S), e.g.

... 5[10] 7[20] ...
... 3[12] 8[?] 4[?] ...
and then
... 5[10] 7[20] ...
... 3[13] 8[18] 4[24] ...

Backward recursion

(This one is easier.) Starting from the bottom row, for each adjacent pair, find the larger number and add it to the upper layer, e.g.

... 5 7 ...
... 3[8] 8[8] 4 ...
and then
... 13 15 ...
... 3[8] 8[8] 4 ...

Definition at line 93 of file 018.cpp.

---

The documentation for this class was generated from the following files:

• 018.cpp
• 067.cpp