Calculate min for a grid starting from top row and going down in 3 directions (down-left, down, down-right).
00 01 02 -> j
10 11 12
20 21 22
calcMin(grid):
if grid == null
|| grid.length() == 0
|| grid[0].length() == 0:
throw
rows = grid.length()
cols = grid[0].length()
mins = new [rows, cols]
calcMins(grid, rows, cols, mins)
min = getMin(mins, cols)
return min
calcMins(grid, rows, cols, mins):
for i = 0, i < rows, i++:
calcMin(grid, rows, cols, i, 0, mins)
calcMin(grid, rows, cols, i, j, mins):
if !(0 <= i < rows):
return null
if !(0 <= j < cols):
return null
if mins[i][j] != null:
return mins[i][j]
min =
checked(
grid[i][j]
+ min(
calcMin(grid, rows, cols, i+1, j-1], mins),
calcMin(grid, rows, cols, i+1, j], mins),
calcMin(grid, rows, cols, i+1, j+1], mins)
)
)
mins[i][j] = min
return min
min(a, b, c):
if a == null && b == null && c == null:
return 0
return
math.min(
a ?? int.max,
b ?? int.max,
c ?? int.max
)
getMin(mins, cols):
min = mins[0][0]
for j = 1, j < cols, j++:
min = math.min(min, mins[0][j])
return min
[Hat tip to SM]
No comments:
Post a Comment