import java.util.ArrayList;
import java.util.List;
// Minimum Path Sum
// We can only move down or right
public class Program {
public static void Print2DList(List<List<Integer>> list2d) {
for (List<Integer> list1d : list2d) {
for (int val : list1d) {
System.out.print(val + " ");
}
System.out.println();
}
}
public static int minPathSum(List<List<Integer>> grid) {
int rows = grid.size();
int cols = grid.get(rows - 1).size();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int current = Integer.MAX_VALUE;
if (i - 1 >= 0) {
current = Math.min(current, grid.get(i - 1).get(j));
}
if (j - 1 >= 0) {
current = Math.min(current, grid.get(i).get(j - 1));
}
if (current == Integer.MAX_VALUE) {
current = 0;
}
grid.get(i).set(j, grid.get(i).get(j) + current);
}
}
Print2DList(grid);
return grid.get(rows - 1).get(cols - 1);
}
public static void main(String[] args) {
List<List<Integer>> grid = new ArrayList<>();
grid.add(new ArrayList<>(List.of(1, 2, 3, 1, 4)));
grid.add(new ArrayList<>(List.of(2, 1, 1, 3, 3)));
grid.add(new ArrayList<>(List.of(3, 2, 2, 1, 5)));
grid.add(new ArrayList<>(List.of(1, 2, 1, 4, 1)));
// [0][0] (1) + [0][1] (2) + [1][1] (1) + [1][2] (1) +
// [2][2] (2) + [2][3] (1) + [3][3] (4) + [3][4] (1) =
// 1 + 2 + 1 + 1 + 2 + 1 + 4 + 1 = 13
System.out.println(minPathSum(grid));
}
}
/*
run:
1 3 6 7 11
3 4 5 8 11
6 6 7 8 13
7 8 8 12 13
13
*/
