Triangle

1public int minimumTotal(List<List<Integer>> triangle) {
2    int n = triangle.size();
3    int[][] dp = new int[n][n];
4
5    // Initialize the last row of DP table
6    for (int i = 0; i < n; i++) {
7        dp[n - 1][i] = triangle.get(n - 1).get(i);
8    }
9
10    // Fill the DP table from bottom to top
11    for (int row = n - 2; row >= 0; row--) {
12        for (int col = 0; col <= row; col++) {
13            dp[row][col] = triangle.get(row).get(col) + Math.min(dp[row + 1][col], dp[row + 1][col + 1]);
14        }
15    }
16
17    // The answer is at the top of the triangle
18    return dp[0][0];
19}