一、题目内容

二、题解

解法1：

思路

dp[i][j] = dp[i][j] + Min(matrix[j],matrix[j])
dfs，要求空间复杂度为O(n)，则说明不能再新建dp矩阵，直接使用matrix

代码

public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        //dp[i][j] = dp[i][j] + Min(matrix[j],matrix[j])
        int m = matrix.length;
        int n = matrix[0].length;
        for(int i = 0; i<m; i++){
            for(int j = 0; j<n; j++){
                if(i == 0 && j == 0){
                    continue;
                }
                if(i == 0){
                    matrix[i][j] += matrix[i][j-1];
                }else if(j == 0){
                    matrix[i][j] += matrix[i-1][j];
                }else {
                    matrix[i][j] += Math.min(matrix[i-1][j],matrix[i][j-1]);
                }
            }
        }
        return matrix[m-1][n-1];
    }
}