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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int MinimumTotal(IList<IList<int>> triangle) {
6 int[] dp = new int[triangle.Count];
7 for (int i = 0; i < triangle[^1].Count; i++) {
8 dp[i] = triangle[^1][i];
9 }
10 for (int row = triangle.Count - 2; row >= 0; row--) {
11 for (int col = 0; col < triangle[row].Count; col++) {
12 dp[col] = triangle[row][col] + Math.Min(dp[col], dp[col + 1]);
13 }
14 }
15 return dp[0];
16 }
17
18 public static void Main() {
19 var solution = new Solution();
20 var triangle = new List<IList<int>> {
21 new List<int> {2},
22 new List<int> {3, 4},
23 new List<int> {6, 5, 7},
24 new List<int> {4, 1, 8, 3}
25 };
26 Console.WriteLine(solution.MinimumTotal(triangle));
27 }
28}The C# solution leverages a dynamic array for path sum calculations. Starting from the last row, the path sum progressively reduces until the top is reached, finalizing in minimal cost stored in dp[0].
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.
1using System;
using System.Collections.Generic;
public class Solution {
private int?[,] memo;
public int MinimumTotal(IList<IList<int>> triangle) {
memo = new int?[triangle.Count, triangle.Count];
return Dfs(0, 0, triangle);
}
private int Dfs(int row, int col, IList<IList<int>> triangle) {
if (row == triangle.Count) return 0;
if (memo[row, col].HasValue) return memo[row, col].Value;
int left = Dfs(row + 1, col, triangle);
int right = Dfs(row + 1, col + 1, triangle);
memo[row, col] = triangle[row][col] + Math.Min(left, right);
return memo[row, col].Value;
}
public static void Main() {
var solution = new Solution();
var triangle = new List<IList<int>> {
new List<int> {2},
new List<int> {3, 4},
new List<int> {6, 5, 7},
new List<int> {4, 1, 8, 3}
};
Console.WriteLine(solution.MinimumTotal(triangle));
}
}C# recursively explores potential paths in the triangle using the Dfs method and pre-saved answers in memo reduce unnecessary recursive calls.