[LeetCode] 120. Triangle

Posted on | In

Problem

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
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

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.

Explanation 1

  1. To clearify, if current value is triangle[i][j] meaning that current row is i, current column is j, then we should go to the minimum of triangle[i+1][j] and triangle[i+1][j+1]. Here, we can use dynamic programming.

  2. Using dynamic programming, we should also need to find out the base case. The base case is when we go to the last row, we just return the value of triangle[lastRow][col].

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    int helper(List<List<Integer>> triangle, int row, int col, Integer[][] memo) {
        if (row == triangle.size()-1) {
            return triangle.get(row).get(col);
        }
        if (memo[row][col] == null) {
            int temp = triangle.get(row).get(col) + Math.min(helper(triangle, row+1, col, memo), helper(triangle, row+1, col+1, memo));
            memo[row][col] = Integer.valueOf(temp);
        }
        return memo[row][col].intValue();
    }
    public int minimumTotal(List<List<Integer>> triangle) {
        Integer[][] memo = new Integer[triangle.size()][triangle.size()];
        return helper(triangle, 0, 0, memo);
    }
}

Explanation 2

  1. We can also save space by creating a one dimensional array have size of the last column, and have values of the last row.

  2. Starting from the second last row back to the first row, loop through its column, its current value triangle.get(row).get(col) changes to adding itself with the minimum value between the dp[col] and dp[col+1] and save the result to dp[col].

  3. At the end, return dp[0].

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[] dp = new int[triangle.size()];
        List<Integer> lastRow = triangle.get(triangle.size()-1);
        dp = lastRow.stream().mapToInt(i->i).toArray();
        for (int row = triangle.size()-2; row >= 0; row--) {
            for (int col = 0; col < triangle.get(row).size(); col++) {
                dp[col] = Math.min(dp[col], dp[col+1]) + triangle.get(row).get(col);
            }
        }
        return dp[0];
    }
}