题解 | #矩阵的最小路径和#
矩阵的最小路径和
http://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb
import java.util.*;
public class Solution {
/**
*
* @param matrix int整型二维数组 the matrix
* @return int整型
*/
public int minPathSum (int[][] matrix) {
// write code here
int m = matrix.length;
matrix[i][n-1] += matrix[i+1][n-1];
matrix[m-1][j] += matrix[m-1][j+1];
}
for(int i = m-2;i>=0;i--){
for(int j = n-2;j>=0;j--){
matrix[i][j] += Math.min(matrix[i+1][j],matrix[i][j+1]);
}
}
return matrix[0][0];
}
}
public class Solution {
/**
*
* @param matrix int整型二维数组 the matrix
* @return int整型
*/
public int minPathSum (int[][] matrix) {
// write code here
int m = matrix.length;
int n = matrix[0].length;
//初始化最后一列
for(int i = m-2;i>=0;i--){matrix[i][n-1] += matrix[i+1][n-1];
}
//初始化最后一行
for(int j = n-2;j>=0;j--){matrix[m-1][j] += matrix[m-1][j+1];
}
for(int i = m-2;i>=0;i--){
for(int j = n-2;j>=0;j--){
matrix[i][j] += Math.min(matrix[i+1][j],matrix[i][j+1]);
}
}
return matrix[0][0];
}
}
