Sponsored
Sponsored
In this approach, we'll use dynamic programming (DP) to achieve the solution. We'll start from the bottom of the triangle and minimize the sum path to the top. We'll keep updating the path sum in a DP array as we move to the top row.
Time Complexity: O(n^2), where n is the number of rows in the triangle.
Space Complexity: O(n), due to the use of the array dp.
1var minimumTotal = function(triangle) {
2 let dp = triangle[triangle.length - 1];
3 for (let row = triangle.length - 2; row >= 0; row--) {
4 for (let col = 0; col < triangle[row].length; col++) {
5 dp[col] = triangle[row][col] + Math.min(dp[col], dp[col + 1]);
6 }
7 }
8 return dp[0];
9};
10
11console.log(minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]));JavaScript's implementation of the DP-based solution iterates from the bottom row. A temporary array dp is used for minimizing the path sum throughout the iterations to the top row.
This approach uses a top-down strategy with memoization to store already computed results, avoiding redundant calculations. Each recursive call stores the minimum path sum starting from the current index down to the base of the triangle.
Time Complexity: O(n^2) (due to memoization)
Space Complexity: O(n^2) for memoization storage.
1var
In JavaScript, the solution comprehensively deploys recursion in combination with memoization to optimize path calculations, allowing paths to be recalculated using previously visited and memoized results.