Min Sum Path in Matrix

• Time : $O(nm)$
• Space : $O(nm)$

c++

int Solution::minPathSum(vector<vector<int>> &A) {
    int n = A.size(), m = A[0].size();
    vector<vector<int>> dp(n,vector<int>(m, INT_MAX));
    dp[0][0] = A[0][0];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(i + 1 < n) dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + A[i+1][j]);
            if(j + 1 < m) dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + A[i][j + 1]);
        }
    }
    return dp[n-1][m-1];
}