Problem Link - Sums in a Triangle
Problem Statement
Given an integer N, let us consider a triangle of numbers of N lines in which a number a_{11} appears in the first line, two numbers a_{21} and a_{22} appear in the second line, three numbers a_{31}, a_{32} and a_{33} appear in the third line, etc. In general, i numbers a_{i1}, a_{i2} \dots a_{ii} appear in the i^{th} line for all 1 \leq i \leq N. Develop a program that will compute the largest of the sums of numbers that appear on the paths starting from the top towards the base, so that:
- on each path the next number is located on the row below, more precisely either directly below or below and one place to the right.
Warning: large Input/Output data, be careful with certain languages
Approach
The code idea is to use dynamic programming to find the maximum path sum. Start by initializing a 2D array to store the maximum sums for each position in the triangle. Populate the last row of this array with the triangle’s last row values. Then, iterate from the second-to-last row to the top, updating each position with the sum of its value and the maximum of the two values directly below it. Finally, the maximum path sum will be stored at the top of the triangle.
Time Complexity
The time complexity is O(N ^2) because each element in the triangle is processed once.
Space Complexity
The space complexity is O(N^2) due to the storage of the 2D array for dynamic programming.