Question

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

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to 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

Java

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];
		}

	}
}

// 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)

120 - Triangle

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions