Min Sum Path in Triangle
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.dynamic_programming;
import java.util.*;
/ * Problem: Min Sum Path in Triangle * Group: 11. Dynamic Programming */ / * ============================================================================================ * PROBLEM: Min Sum Path in Triangle * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given a triangle array. Find the minimum path sum from top to bottom. * Movement: From (row, i), you can move to (row+1, i) or (row+1, i+1). * * --------------------- * 2. Logical Breakdown * --------------------- * It is best to solve this Bottom-Up. * Let dp[row][i] be the min path sum from (row, i) to the bottom. * * Recurrence: * dp[row][i] = triangle[row][i] + min(dp[row+1][i], dp[row+1][i+1]) * * Base Case: * The last row's dp values are simply the values in the triangle itself * (distance to bottom is 0). * * --------------------- * 3. Complexity * --------------------- * Time: O(N^2) (Total elements in triangle) * Space: O(N) (If we only store the next row's results). * * ============================================================================================ */ public class MinSumPathInTriangle { public int solve(int A) { // TODO: Implement solution return 0; }
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
return 1;
}
}