[InterviewBit] Min Sum Path in Matrix

Min Sum Path in Matrix

  • Time :
  • Space :
1
2
3
4
5
6
7
8
9
10
11
12
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];
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/09/11/PS/interviewbit/min-sum-path-in-matrix/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.