Problem:

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:

Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

Idea:

DP

Solution 1:

C++ / Recursion with memoization

Time complexity: O(mn)

Space complexity: O(mn)

Solution 2:

C++ / DP

Time complexity: O(mn)

Space complexity: O(1)

Related Problems:

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website

Paypal
Venmo
huahualeetcode

## One Comment

1. David Huang July 22, 2018

Nice codes and explanation, Thank you Huahua.

Changes for solution 1
a)change the order of x and y. (Don’t know why you switch them:))
b) Remove unused arguments m and n.

The following codes were accepted too.

class Solution {
public:
int minPathSum(vector<vector>& grid) {
int m = grid.size();
if (m == 0) return 0;
int n = grid[0].size();

s_ = vector<vector>(m, vector(n, 0));

return minPathSum(grid, m – 1, n – 1);
}
private:
long minPathSum(const vector<vector>& grid,
int x, int y) {
if (x == 0 && y == 0) return grid[y][x];
if (x < 0 || y 0) return s_[x][y];

int ans = grid[x][y] + min(minPathSum(grid, x – 1, y),
minPathSum(grid, x, y – 1));
return s_[x][y] = ans;
}

vector<vector> s_;
};