Unique Paths in a Grid

mediumSave

CombinatoricsDynamic ProgrammingMatrix

Given an m x n grid, filled with non-negative integers representing the cost to traverse through specific points, calculate the minimum cost path from the top-left corner to the bottom-right corner. You can only move either down or right at any point in time.

Example 1

Input

[
  "[[1, 3, 1], [1, 5, 1], [4, 2, 1]]"
]

Output

Explanation. The path with minimum total cost is 1->3->1->1->1 which sums up to 7.

Example 2

Input

[
  "[[1, 2], [5, 6]]"
]

Output

Explanation. The path with minimum total cost is 1->2->6 totaling 7.

Example 3

Input

[
  "[[1, 2, 3], [4, 5, 6], [7, 8, 9]]"
]

Output

Explanation. The path with minimum total cost is straight down the left column and across the bottom row, with cost 1+4+7+8+9 = 29. However, following 1->2->3->6->9 results in the least cost of 21.

Follow-up: How would the solution change if movement to the left or upwards was also allowed?

Constraints:

1. `1 <= m, n <= 200` 2. Each value in the grid represents the cost and will be a non-negative integer.

Views: 3