Question

Formatted question description: https://leetcode.ca/all/120.html

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]]
Output: -10

Constraints:

1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-10⁴ <= triangle[i][j] <= 10⁴

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

Algorithm

Each node can go down only the two numbers adjacent to it, so each position (i, j) can only come from the two positions adjacent to it in the upper layer, which is (i-1 , j-1) and (i-1, j) these two positions, then the state transition equation is:

triangle[i][j] = min(triangle[i-1][j-1], triangle[i-1][j])

We update from the second line. Note that the numbers on both sides are directly assigned to the boundary value of the previous line. In the end, we only need to find the number with the smallest value at the bottom layer, which is the global smallest path sum.

Code

import java.util.List;

public class Triangle {

	public class Solution {
	    public int minimumTotal(List<List<Integer>> triangle) {

	    	if (triangle.size() == 0) {
	    		return 0;
	    	}

	    	// re-use each row of input, if input can be modified
	    	for (int i = 1; i < triangle.size(); i++) { // @ note: starts at index=1

	    		List<Integer> prevRow = triangle.get(i - 1);
	    		List<Integer> currentRow = triangle.get(i);

	    		for (int j = 0; j < currentRow.size(); j++) {
	    			int upLeft = j - 1 >= 0 ? prevRow.get(j - 1) : Integer.MAX_VALUE;
	    			int upRight = j < prevRow.size() ? prevRow.get(j) : Integer.MAX_VALUE;

	    			currentRow.set(j, currentRow.get(j) + Math.min(upLeft, upRight));
	    		}
	    	}

	    	int min = Integer.MAX_VALUE;
	    	for (int each: triangle.get(triangle.size() - 1)) {
	    		min = Math.min(min, each);
	    	}

	    	return min;
	    }
	}

	// O(n) extra space
	public class Solution_not_modifying_input {
		public int minimumTotal(List<List<Integer>> triangle) {

			int lastIndex = triangle.size() - 1;
			int[] row = new int[triangle.get(lastIndex).size()];

			// fill with last row, i.e. longest row
			for (int i = 0; i < triangle.get(lastIndex).size(); i++) {
				row[i] = triangle.get(lastIndex).get(i);
			}

			// iterate from last second row
			for (int i = triangle.size() - 2; i >= 0; i--) {

				List<Integer> currentRow = triangle.get(i);

				for (int j = 0; j < triangle.get(i + 1).size() - 1; j++) {
					row[j] = currentRow.get(j) + Math.min(row[j], row[j + 1]);
				}
			}

			return row[0];
		}

	}
}

############

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

// OJ: https://leetcode.com/problems/triangle/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int minimumTotal(vector<vector<int>>& A) {
        for (int N = A.size(), i = N - 2; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                A[i][j] += min(A[i + 1][j], A[i + 1][j + 1]);
            }
        }
        return A[0][0];
    }
};

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        dp = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            for j in range(i + 1):
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]
        return dp[0]

############

class Solution(object):
  def minimumTotal(self, triangle):
    """
    :type triangle: List[List[int]]
    :rtype: int
    """
    dp = [0] * len(triangle)
    dp[0] = triangle[0][0]
    for i in range(1, len(triangle)):
      pre = dp[0]
      for j in range(len(triangle[i])):
        tmp = dp[j]
        if j == 0:
          dp[j] = pre
        elif j == len(triangle[i]) - 1:
          dp[j] = pre
        else:
          dp[j] = min(dp[j], pre)
        dp[j] += triangle[i][j]
        pre = tmp
    return min(dp)

func minimumTotal(triangle [][]int) int {
	n := len(triangle)
	dp := make([]int, n+1)
	for i := n - 1; i >= 0; i-- {
		for j := 0; j <= i; j++ {
			dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
		}
	}
	return dp[0]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

function minimumTotal(triangle: number[][]): number {
    const n = triangle.length;
    for (let i = n - 2; i >= 0; i--) {
        for (let j = 0; j < i + 1; j++) {
            triangle[i][j] += Math.min(
                triangle[i + 1][j],
                triangle[i + 1][j + 1],
            );
        }
    }
    return triangle[0][0];
}

impl Solution {
    pub fn minimum_total(mut triangle: Vec<Vec<i32>>) -> i32 {
        let n = triangle.len();
        for i in (0..n - 1).rev() {
            for j in 0..i + 1 {
                triangle[i][j] += triangle[i + 1][j].min(triangle[i + 1][j + 1]);
            }
        }
        triangle[0][0]
    }
}

120 - Triangle

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions