417. The Cheapest Fall Through a Triangle
A triangle of numbers has one entry in its first row, two in its second, and so on. Start at the single top entry and fall to the bottom, moving at each step to one of the two entries directly below. Print the smallest total of the entries visited.
2
3 4
6 5 7
4 1 8 3
The best fall is 2 + 3 + 5 + 1 = 11.
Greedy from the top fails on that very triangle: it picks 3 over 4, then 5 over 7, then 1, which happens to be right here, but reverse the last row and it is not. Taking the smaller neighbour cannot see what lies two rows below.
Work from the BOTTOM instead, which removes all the awkwardness. Replace each entry by the cheapest fall starting from it:
best[last row] = the row itself
best[i][j] = triangle[i][j] + min( best[i+1][j], best[i+1][j+1] )
and the answer is best[0][0].
Going bottom-up means each entry's two successors are already final when it is computed, so there is no ordering question and no memo table to manage. Top-down with memoisation gives the same answer and needs more care.
Values may be negative, so the answer may be negative and no running minimum should start at zero.
Constraints - `1 ≤ r ≤ 300` - `-10000 ≤ entry ≤ 10000`
Input
The first line contains an integer r, the number of rows.
Each of the next r lines contains one more integer than the last, the entries of that row.
Output
Print the smallest total of any fall from the top entry to the bottom row.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.