120. Triangle #

Problem #

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.

Problem Summary #

Given a triangle, find the minimum path sum from top to bottom. Each step can only move to an adjacent node in the row below.

Solution Approach #

Find the minimum sum from the top to the bottom of the triangle. It is best to use O(n) time complexity.
The optimal solution to this problem uses no auxiliary space and directly works from the lower rows upward. The ordinary solution uses a two-dimensional array DP, and a slightly optimized solution uses a one-dimensional array DP. The solutions are as follows:

Code #


package leetcode

import (
	"math"
)

// Solution 1: reverse-order DP, no extra space
func minimumTotal(triangle [][]int) int {
	if triangle == nil {
		return 0
	}
	for row := len(triangle) - 2; row >= 0; row-- {
		for col := 0; col < len(triangle[row]); col++ {
			triangle[row][col] += min(triangle[row+1][col], triangle[row+1][col+1])
		}
	}
	return triangle[0][0]
}

// Solution 2: standard DP, space complexity O(n)
func minimumTotal1(triangle [][]int) int {
	if len(triangle) == 0 {
		return 0
	}
	dp, minNum, index := make([]int, len(triangle[len(triangle)-1])), math.MaxInt64, 0
	for ; index < len(triangle[0]); index++ {
		dp[index] = triangle[0][index]
	}
	for i := 1; i < len(triangle); i++ {
		for j := len(triangle[i]) - 1; j >= 0; j-- {
			if j == 0 {
				// leftmost
				dp[j] += triangle[i][0]
			} else if j == len(triangle[i])-1 {
				// rightmost
				dp[j] += dp[j-1] + triangle[i][j]
			} else {
				// middle
				dp[j] = min(dp[j-1]+triangle[i][j], dp[j]+triangle[i][j])
			}
		}
	}
	for i := 0; i < len(dp); i++ {
		if dp[i] < minNum {
			minNum = dp[i]
		}
	}
	return minNum
}