Welcome to Subscribe On Youtube
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
-104 <= triangle[i][j] <= 104
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] } }