动态规划的经典问题,目的地的最优解,等于左边的最优解和上边的最优解的最小值。需要开辟一个二维数组,记录每个节点的最优解。
public int minPathSum(int[][] matrix) { int[][] arr = new int[matrix.length][matrix[0].length]; arr[0][0] = matrix[0][0]; // 初始化两边,避免在第三个循环中做过多的判断 for (int i = 1; i < matrix.length; i++) { arr[i][0] = matrix[i][0] + arr[i - 1][0]; } for (int i = 1; i < matrix[0].length; i++) { arr[0][i] = matrix[0][i] + arr[0][i - 1]; } for (int i = 1; i < matrix.length; i++) { for (int j = 1; j < matrix[i].length; j++) { if (arr[i - 1][j] > arr[i][j - 1]) { arr[i][j] = arr[i][j - 1] + matrix[i][j]; }else{ arr[i][j] = arr[i-1][j ] + matrix[i][j]; } } } return arr[matrix.length - 1][matrix[0].length - 1]; }