This is a typical DP problem. Suppose the minimum path sum of arriving at point (i, j) is S[i][j], then the state equation is S[i][j] = min(S[i - 1][j], S[i][j - 1]) + grid[i][j].
Well, some boundary conditions need to be handled. The boundary conditions happen on the topmost row (S[i - 1][j] does not exist) and the leftmost column (S[i][j - 1] does not exist). Suppose grid is like [1, 1, 1, 1], then the minimum sum to arrive at each point is simply an accumulation of previous points and the result is [1, 2, 3, 4].
Now we can write down the following (unoptimized) code.
1 class Solution { 2 public: 3 int minPathSum(vector<vector<int>>& grid) { 4 int m = grid.size(); 5 int n = grid[0].size(); 6 vector<vector<int> > sum(m, vector<int>(n, grid[0][0])); 7 for (int i = 1; i < m; i++) 8 sum[i][0] = sum[i - 1][0] + grid[i][0]; 9 for (int j = 1; j < n; j++) 10 sum[0][j] = sum[0][j - 1] + grid[0][j]; 11 for (int i = 1; i < m; i++) 12 for (int j = 1; j < n; j++) 13 sum[i][j] = min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j]; 14 return sum[m - 1][n - 1]; 15 } 16 };
As can be seen, each time when we update sum[i][j], we only need sum[i - 1][j] (at the current column) and sum[i][j - 1] (at the left column). So we need not maintain the full m*nmatrix. Maintaining two columns is enough and now we have the following code.
1 class Solution { 2 public: 3 int minPathSum(vector<vector<int>>& grid) { 4 int m = grid.size(); 5 int n = grid[0].size(); 6 vector<int> pre(m, grid[0][0]); 7 vector<int> cur(m, 0); 8 for (int i = 1; i < m; i++) 9 pre[i] = pre[i - 1] + grid[i][0]; 10 for (int j = 1; j < n; j++) { 11 cur[0] = pre[0] + grid[0][j]; 12 for (int i = 1; i < m; i++) 13 cur[i] = min(cur[i - 1], pre[i]) + grid[i][j]; 14 swap(pre, cur); 15 } 16 return pre[m - 1]; 17 } 18 };
Further inspecting the above code, it can be seen that maintaining pre is for recovering pre[i], which is simply cur[i] before its update. So it is enough to use only one vector. Now the space is further optimized and the code also gets shorter.
1 class Solution { 2 public: 3 int minPathSum(vector<vector<int>>& grid) { 4 int m = grid.size(); 5 int n = grid[0].size(); 6 vector<int> cur(m, grid[0][0]); 7 for (int i = 1; i < m; i++) 8 cur[i] = cur[i - 1] + grid[i][0]; 9 for (int j = 1; j < n; j++) { 10 cur[0] += grid[0][j]; 11 for (int i = 1; i < m; i++) 12 cur[i] = min(cur[i - 1], cur[i]) + grid[i][j]; 13 } 14 return cur[m - 1]; 15 } 16 };