Unique Paths in a Grid

mediumSave

ArrayDynamic ProgrammingMatrix

Given a m x n grid filled with non-negative numbers, find a path from the top left to the bottom right which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time.

Example 1

Input

Output

Explanation. The path 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum. So, the minimum path sum is 7.

Example 2

Input

Output

Explanation. The path 1 -> 2 -> 4 is the least sum path resulting in a path sum of 7.

Example 3

Input

[
  [
    1
  ]
]

Output

Explanation. There is only one cell in this grid, so the minimum path sum is the value of that single cell which is 1.

Follow-up: Can you solve this problem in O(m * n) time complexity with O(n) space complexity, where `m` is the number of rows and `n` is the number of columns?

Constraints:

1. The grid will always be at least `1 x 1` size.\n2. All numbers in the grid will be non-negative integers.

Views: 1