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_;
};