Leetcode - Triangle
https://leetcode.com/problems/triangle/
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | func minimumTotal(nums [][]int) int { if len(nums) == 0 { return 0 } n := len(nums) dp := make([][]int, n) for i := 0; i < len(dp); i++ { dp[i] = make([]int, i+1) } dp[0][0] = nums[0][0] for i := 1; i < n; i++ { for j := 0; j < len(dp[i]); j++ { if j != 0 && j != len(dp[i])-1 { dp[i][j] = nums[i][j] + min(dp[i-1][j-1], dp[i-1][j]) } if j == 0 { dp[i][j] = nums[i][j] + dp[i-1][j] } if j == len(dp[i])-1 { dp[i][j] = nums[i][j] + dp[i-1][j-1] } } } //fmt.Println("dp: ", dp) return min(dp[n-1]...)}func min(nums ...int) int { minNum := nums[0] for _, n := range nums { if minNum > n { minNum = n } } return minNum} |
3 年前