Similar problem to Unique Path problem
We can use the same approach
The difference we store the path sum instead of the number of paths
[i][j-1]
|
[i-1][j] - [i][j]
minPathToPosition[i][j] = grid[i-1][j-1] + min(minPathToPosition[i - 1][j], minPathToPosition[i][j - 1])
and for the first row and first column we could not use the default 0 value in the extra row/column
We can only shift left for first row cells and only shift down for first columns cells
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q064MinimumPathSum.playground/Contents.swift
No comments:
Post a Comment