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.
1import java.util.List;
2
3class Solution {
4 public int minimumTotal(List<List<Integer>> triangle) {
5 int[] dp = new int[triangle.size()];
6 for (int i = 0; i < triangle.get(triangle.size() - 1).size(); i++) {
7 dp[i] = triangle.get(triangle.size() - 1).get(i);
8 }
9 for (int row = triangle.size() - 2; row >= 0; row--) {
10 for (int col = 0; col < triangle.get(row).size(); col++) {
11 dp[col] = triangle.get(row).get(col) + Math.min(dp[col], dp[col + 1]);
12 }
13 }
14 return dp[0];
15 }
16
17 public static void main(String[] args) {
18 Solution sol = new Solution();
19 List<List<Integer>> triangle = List.of(
20 List.of(2), List.of(3, 4), List.of(6, 5, 7), List.of(4, 1, 8, 3)
21 );
22 System.out.println(sol.minimumTotal(triangle));
23 }
24}The Java solution iterates from the triangle's bottom row to the top, minimizing path sums. We store temporary results in a 1D array dp, updating values based on current and next possibilities.
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.
1#
This C code applies a memoization approach, leveraging recursion through dfs to calculate and store intermediate results in memo, exploring both potential paths per cell.