64. Minimum Path Sum

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:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

dp state transition: dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

// Dynamic Programming
int minPathSum(vector<vector<int>>& grid) { // time: O(m * n); space: O(m * n)
    if (grid.empty() || grid[0].empty()) return 0;
    int m = grid.size(), n = grid[0].size();
    vector<vector<int> > sum(m, vector<int>(n, 0));
    for (int i = 0; i < m; ++i)
        sum[i][0] = grid[i][0] + (i >= 1 ? sum[i - 1][0] : 0);
    for (int j = 1; j < n; ++j)
        sum[0][j] = grid[0][j] + sum[0][j - 1];
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            sum[i][j] = min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j];
        }
    }
    return sum.back().back();
}

// Space Optimized Dynamic Programming
int minPathSum(vector<vector<int>>& grid) { // time: O(m*n); space: O(n)
    if (grid.empty() || grid[0].empty()) return 0;
    int m = grid.size(), n = grid[0].size();
    vector<int> dp(n, 0);
    for (int j = 0; j < n; ++j) dp[j] = grid[0][j] + (j > 0 ? dp[j - 1] : 0);
    for (int i = 1; i < m; ++i) {
        dp[0] += grid[i][0];
        for (int j = 1; j < n; ++j) {
            dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
        }
    }
    return dp.back();
}

int minPathSum(vector<vector<int>>& grid) { // time: O(m*n); space: O(m*n)
    if (grid.empty() || grid[0].empty()) return 0;
    int m = grid.size(), n = grid[0].size();
    vector<vector<int> > sum(m, vector<int>(n, 0));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == 0)
                sum[0][j] = grid[0][j] + (j > 0 ? sum[0][j - 1] : 0);
            else if (j == 0)
                sum[i][0] = grid[i][0] + (i > 0 ? sum[i - 1][0] : 0);
            else
                sum[i][j] = min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j];
        }
    }
    return sum.back().back();
}

int minPathSum(vector<vector<int>>& grid) { // time: O(m*n); space: O(n)
    if (grid.empty() || grid[0].empty()) return 0;
    int m = grid.size(), n = grid[0].size();
    vector<int> sum(n, 0);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == 0)
                sum[j] = grid[i][j] + (j > 0 ? sum[j - 1] : 0);
            else if (j == 0)
                sum[j] += grid[i][j];
            else
                sum[j] = min(sum[j], sum[j - 1]) + grid[i][j];
        }
    }
    return sum.back();
}