public static void main(String[] args) {

int[][] grid = new int[][] {

new int[]{7, 0, 8, 8, 0, 3, 5, 8, 5, 4},

new int[]{4, 1, 2, 9, 9, 6, 0, 8, 6, 9},

new int[]{9, 7, 1, 1, 0, 1, 2, 4, 1, 7}

}

;

System.out.println(Arrays.deepToString(grid).replaceAll("], ", "],\n"));

System.out.println(new Solution64().minPathSum(grid));

}

public int minPathSum(int[][] grid) {

// 应该是先找出一条作为最小值，然后比这个大的就没必要再找了

// 看看能不能把递归化成平的

final int length1 = grid.length;

final int length2 = grid[0].length;

final int[][] totalArray = new int[grid.length][grid[0].length];

// find a way

int min = 0;

for (int i = 0; i < length1; i++) {

min += grid[i][0];

totalArray[i][0] = min;

}

for (int j = 1; j < length2; j++) {

min += grid[length1 - 1][j];

totalArray[length1 - 1][j] = min;

totalArray[0][j] = totalArray[0][j - 1] + grid[0][j];

}

// find all way

int total = 0;

for (int i = 1; i < length1; i++) {

for (int j = 0; j < length2; j++) {

if (j == 0) {

totalArray[i][j] = totalArray[i - 1][j] + grid[i][j];

} else {

totalArray[i][j] =

Math.min(totalArray[i - 1][j], totalArray[i][j - 1])

+ grid[i][j];

}

System.out.println(Arrays.deepToString(totalArray).replaceAll("], ", "],\n").replaceAll("]]", "]\n]").replaceAll("\\[\\[", "[\n["));

// if (totalArray[i][j] > min) {

// // System.out.println("break");

// break;

// }

}

}

System.out.println(Arrays.deepToString(grid).replaceAll("], ", "],\n").replaceAll("]]", "]\n]").replaceAll("\\[\\[", "[\n["));

System.out.println(Arrays.deepToString(totalArray).replaceAll("], ", "],\n"));

return totalArray[length1 - 1][length2 - 1];

}