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.
1#include <stdio.h>
2#include <limits.h>
3
4int minimumTotal(int** triangle, int triangleSize, int* triangleColSize) {
5 int dp[triangleSize];
6 for (int i = 0; i < triangleColSize[triangleSize - 1]; ++i) {
7 dp[i] = triangle[triangleSize - 1][i];
8 }
9
10 for (int row = triangleSize - 2; row >= 0; --row) {
11 for (int col = 0; col < triangleColSize[row]; ++col) {
12 dp[col] = triangle[row][col] + (dp[col] < dp[col + 1] ? dp[col] : dp[col + 1]);
13 }
14 }
15 return dp[0];
16}
17
18int main() {
19 int t1[] = {2};
20 int t2[] = {3, 4};
21 int t3[] = {6, 5, 7};
22 int t4[] = {4, 1, 8, 3};
23
24 int* triangle[] = {t1, t2, t3, t4};
25 int columnSize[] = {1, 2, 3, 4};
26
27 int result = minimumTotal(triangle, 4, columnSize);
28 printf("%d\n", result);
29
30 return 0;
31}The function minimumTotal takes a 2D array representing the triangle and its size and calculates the minimum path sum using a bottom-up DP strategy. We utilize an array dp which holds the path sums for the current row. We iterate from the last row to the first, updating dp till the top.
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#include <vector>
2#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int memo[201][201];
class Solution {
public:
int dfs(int row, int col, vector<vector<int>>& triangle) {
if (row == triangle.size()) return 0;
if (memo[row][col] != -1) return memo[row][col];
int left = dfs(row + 1, col, triangle);
int right = dfs(row + 1, col + 1, triangle);
memo[row][col] = triangle[row][col] + min(left, right);
return memo[row][col];
}
int minimumTotal(vector<vector<int>>& triangle) {
memset(memo, -1, sizeof(memo));
return dfs(0, 0, triangle);
}
};
int main() {
Solution sol;
vector<vector<int>> triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
cout << sol.minimumTotal(triangle) << endl;
return 0;
}C++ implementation uses recursion with memoization to compute minimum path sums from top to leaf nodes. dfs efficiently computes in bottom paths using the array memo to eliminate redundant calculations.