LeetCode medium 120. Triangle (Dynamic Programming)
Question:
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.
I always get
fatal error: Can’t form Range with end < start
on “for i in (row-1)…0”.
Thank you so much! Appreciate your time!
class Solution { func minimumTotal(triangle: [[Int]]) -> Int { if triangle.count == 0 { return 0 } if triangle.count == 1 { return triangle[0][0] } var arr = [Int](count: triangle.last!.count, repeatedValue: 0) let row = triangle.count for i in (row-1)...0 { let col = triangle[i].count for j in 0...col-1 { if i == row-1 { arr[i] = triangle[i][j] continue } arr[j] = min(arr[j], arr[j+1]) + triangle[i][j] } } return arr[0] } } var test1 = Solution() //var input = [[10]] //var input = [[1],[2,3]] var input = [[-1],[2,3],[1,-1,-3]] var result = test1.minimumTotal(input) print(result)
Answer
for in (0...row-1).reverse()
Swift can’t read row-1…0