Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

  1. [
  2.      [2],
  3.     [3,4],
  4.    [6,5,7],
  5.   [4,1,8,3]
  6. ]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Solution:

  1. public class Solution {
  2.   public int minimumTotal(List<List<Integer>> triangle) {
  3.     int n = triangle.size();
  5.     int[] arr = new int[n];
  7.     for (int i = 0; i < n; i++) {
  8.       arr[i] = triangle.get(n - 1).get(i);
  9.     }
  11.     for (int i = n - 2; i >= 0; i--) {
  12.       for (int j = 0; j <= i; j++) {
  13.         arr[j] = Math.min(arr[j], arr[j + 1]) + triangle.get(i).get(j);
  14.       }
  15.     }
  17.     return arr[0];
  18.   }
  19. }