Medium
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100
defmodule Solution do
@spec min_path_sum(grid :: [[integer]]) :: integer
def min_path_sum(grid) do
traverse(grid, [0 | List.duplicate(20000, 199)])
end
defp traverse([], prev_row), do: Enum.at(prev_row, -1)
defp traverse([[first | row] | rows], [prev_row_head | prev_row]) do
prev_row = traverse_row(row, prev_row, [first + prev_row_head])
traverse(rows, prev_row)
end
defp traverse_row([], _prev_row, acc), do: Enum.reverse(acc)
defp traverse_row([head | tail], [top | prev_row], [prev | _rest] = acc) do
traverse_row(tail, prev_row, [head + min(prev, top) | acc])
end
end