DevExCode

2647. Color the Triangle Red

ArrayMath

Explanation:

To solve this problem, we can use dynamic programming with a bottom-up approach. We can start from the bottom row of the triangle and then move up row by row, calculating the maximum sum path that ends at each cell. We can update each cell with the sum of the current cell value and the maximum of the two possible parent cells from the row below. Finally, the answer will be the maximum value in the top row.

Here are the step-by-step iterations:

  1. Start from the bottom row and fill it with the given values.
  2. For each cell in the above row, update it to be the sum of the current value and the maximum of the two parent cells from the row below.
  3. Repeat step 2 for each row until we reach the top row.
  4. The answer will be the maximum value in the top row.

Time complexity: O(n^2) where n is the number of rows in the triangle. Space complexity: O(n) for storing the intermediate results in the current row.

: :

View Leetcode Problem
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n];
        
        for (int i = 0; i < n; i++) {
            dp[i] = triangle.get(n - 1).get(i);
        }
        
        for (int row = n - 2; row >= 0; row--) {
            for (int i = 0; i <= row; i++) {
                dp[i] = triangle.get(row).get(i) + Math.min(dp[i], dp[i + 1]);
            }
        }
        
        return dp[0];
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question