【牛客题霸题解】矩阵的最小路径和

设表示走到位置需要的最小路径和
那首先，第一行和第一列是确定的，其余位置
但是可以发现，其实不用新开辟一个dp数组，直接在原数组上更新也可以
c++

class Solution {
public:

    int minPathSum(vector<vector<int> >& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        for(int i = 1 ; i < n ; i++){matrix[i][0] = matrix[i-1][0]+ matrix[i][0];}
        for(int j = 1 ; j < m ; j++){matrix[0][j] = matrix[0][j-1]+  matrix[0][j];}
        for(int i = 1 ; i < n ; i++)
        {
              for(int j = 1 ; j < m ; j++)
              {
                      matrix[i][j] = min(matrix[i-1][j],matrix[i][j-1])+matrix[i][j];
              }
        }

        return matrix[n-1][m-1];
    }
};

java

import java.util.*;
public class Solution {
    public int minPathSum (int[][] matrix) {
        // write code here
        int n = matrix.length;
        int m = matrix[0].length;
        for(int i = 1 ; i < n ; i++){matrix[i][0] = matrix[i-1][0]+ matrix[i][0];}
        for(int j = 1 ; j < m ; j++){matrix[0][j] = matrix[0][j-1]+  matrix[0][j];}
        for(int i = 1 ; i < n ; i++)
        {
              for(int j = 1 ; j < m ; j++)
              {
                      matrix[i][j] = Math.min(matrix[i-1][j],matrix[i][j-1])+matrix[i][j];
              }
        }

        return matrix[n-1][m-1];
    }
}

python

class Solution:
    def minPathSum(self , matrix ):
        n = len(matrix);
        m = len(matrix[0]);
        for i in range(1,n):
            matrix[i][0] = matrix[i-1][0]+matrix[i][0]
        for j in range(1,m):
            matrix[0][j] = matrix[0][j-1]+matrix[0][j]
        for i in range(1,n):
            for j in range(1,m):
                matrix[i][j] = min(matrix[i-1][j],matrix[i][j-1])+matrix[i][j];
        return matrix[n-1][m-1];