Code : Minimum Path Sum

class Solution {
  public:
    int minPathSum(vector<vector<int>> &mat);
};

int Solution ::minPathSum(vector<vector<int>> &mat) {
    int row = mat.size(), col = mat[0].size();

    // dp[i][j] is the minimum path sum when the journey ends at cell (i, j)
    vector<vector<int>> dp(row, vector<int>(col, 0));

    // Base Case : Manually fill first row and first column
    dp[0][0] = mat[0][0];
    for (int j = 1; j < col; j++) {
        dp[0][j] = mat[0][j] + dp[0][j - 1];
    }
    for (int i = 1; i < row; i++) {
        dp[i][0] = mat[i][0] + dp[i - 1][0];
    }

    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            // You must've come to this cell from left or up.
            dp[i][j] = mat[i][j] + min(dp[i][j - 1], dp[i - 1][j]);
        }
    }

    return dp[row - 1][col - 1];
}

class Solution {
  public:
    int minPathSum(vector<vector<int>> &mat);
};

int Solution ::minPathSum(vector<vector<int>> &mat) {
    int row = mat.size(), col = mat[0].size();

    // dp[i][j] is the minimum path sum when the journey start at cell (i, j).
    // It is implicit that the journey always end at (row - 1, col - 1).
    vector<vector<int>> dp(row, vector<int>(col, 0));

    // Base Case : Manually fill last row and last column
    dp[row - 1][col - 1] = mat[row - 1][col - 1];
    for (int j = col - 2; j >= 0; j--) {
        dp[row - 1][j] = mat[row - 1][j] + dp[row - 1][j + 1];
    }
    for (int i = row - 2; i >= 0; i--) {
        dp[i][col - 1] = mat[i][col - 1] + dp[i + 1][col - 1];
    }

    for (int i = row - 2; i >= 0; i--) {
        for (int j = col - 2; j >= 0; j--) {
            // You must've come to this cell from left or up.
            dp[i][j] = mat[i][j] + min(dp[i][j + 1], dp[i + 1][j]);
        }
    }

    return dp[0][0];
}