Unique Paths in a Grid
mediumSave
CombinatoricsDynamic ProgrammingMatrix
Given a m x n grid filled with non-negative numbers, find a path from the top left corner to the bottom right corner, 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
[ [ 1, 3, 1 ], [ 1, 5, 1 ], [ 4, 2, 1 ] ]
Output
7
Explanation. The path 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum which is 7.
Example 2
Input
[ [ 1, 2, 5 ], [ 3, 2, 1 ] ]
Output
6
Explanation. The path 1 -> 2 -> 2 -> 1 minimizes the sum, which is 6.
Follow-up: Can you find a solution which works in `O(n * m)` time complexity?
Constraints:
1. The number of rows `m` and columns `n` are both at least 1 and at most 100. 2. Each cell contains a non-negative integer less than or equal to 100.
- Views
- 3