Calculating the Minimum Sum Path in a Triangle (LeetCode Problem) Given a triangle array, return the minimum path sum from top to bottom. For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row. public static int minSumPathMemo(int[][] triangle) This method will calculate the minimum sum path in the triangle using the top down strategy. Note this method MUST BE recursive and you will need to create a recursive helper method. public static int minSumPathBottomUp(int[][] triangle) This method will calculate the minimum sum path in the triangle using the bottom up strategy. Note this method CANNOT be recursive and you should not create any additional helper functions. Extra Challenge: Could you do this using only O(n) extra space where n is the total number of rows in the triangle? This is method signature class below: package dynamic; public class MinSumPath { public static int minSumPathMemo(int triangle[][]) { return 0; } public static int minSumPathBottomUp(int triangle[][]) { return 0; } }
Calculating the Minimum Sum Path in a Triangle (LeetCode Problem)
Given a triangle array, return the minimum path sum from top to bottom. For each step, you may move to
an adjacent number of the row below. More formally, if you are on index i on the current row, you may
move to either index i or index i + 1 on the next row.
public static int minSumPathMemo(int[][] triangle)
This method will calculate the minimum sum path in the triangle using the top down strategy. Note this
method MUST BE recursive and you will need to create a recursive helper method.
public static int minSumPathBottomUp(int[][] triangle)
This method will calculate the minimum sum path in the triangle using the bottom up strategy. Note this
method CANNOT be recursive and you should not create any additional helper functions.
Extra Challenge: Could you do this using only O(n) extra space where n is the total number of rows in the
triangle?
This is method signature class below:
package dynamic;
public class MinSumPath {
public static int minSumPathMemo(int triangle[][]) {
return 0;
}
public static int minSumPathBottomUp(int triangle[][]) {
return 0;
}
}
![Example 1
Input: triangle = [[2], [3,4], [6,5,7], [4, 1,8,3]]
Output: 11
Explanation: The triangle looks like:
2
34
657
4 18 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above)
Example 2:
Input: triangle
Output: -10
=
[[-10]]
Note that triangle [0] has length 1 and triangle[i].length triangle [i-1].length+1. Your
methods should work correctly for any input where the triangle length is between 1 and 200 (inclusively).
The triangle can contain numbers between -10000 and 10000.
=](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F165f5551-99fc-4800-9810-1597ce53807c%2F9d976f2e-d803-4ae5-bad4-8d656d9b8628%2F09gum2_processed.png&w=3840&q=75)
Trending now
This is a popular solution!
Step by step
Solved in 6 steps with 4 images
