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 <vector>
2#include <algorithm>
3#include <iostream>
4using namespace std;
5
6class Solution {
7public:
8 int minimumTotal(vector<vector<int>>& triangle) {
9 vector<int> dp(triangle.back());
10 for (int row = triangle.size() - 2; row >= 0; --row) {
11 for (int col = 0; col < triangle[row].size(); ++col) {
12 dp[col] = triangle[row][col] + min(dp[col], dp[col + 1]);
13 }
14 }
15 return dp[0];
16 }
17};
18
19int main() {
20 Solution sol;
21 vector<vector<int>> triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
22 cout << sol.minimumTotal(triangle) << endl;
23 return 0;
24}The solution class provides a method minimumTotal which calculates the minimum path sum using a 1D DP approach. The process is from bottom to top, continuously updating the dp array with the minimum sum we can have up to each cell.
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.
1def
Python's iterative function utilizes a multi-layered array memo, storing inter-path computations to enhance speed. The primary recursive dfs function checks memo for known results prior to recursive descent.