LeetCode-in-All

64. Minimum Path Sum

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.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

Solution

defmodule Solution do
  @spec min_path_sum(grid :: [[integer]]) :: integer
  def min_path_sum(grid) do
    grid_width = length(hd(grid)) # Determine the number of columns in the grid
    traverse(grid, [0 | List.duplicate(:infinity, grid_width - 1)])
  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

This site is open source. Improve this page.