Leetcode: 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

[
     [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.

Understand the problem:
As described by the 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.
So the key to understand this problem is to know what is adjacent numbers?
For index = 1 in row i, the adjacent numbers that 1 can go is index 0, 1, 2 on row i + 1. 

In addition, the problem allows negative numbers in the triangle, so we must consider all possible paths. 

However, after reading some posts, I found that the adjacent numbers for A[ i ][ j ] is actually A[ i + 1 ][ j ] and A[ i + 1 ] [ j + 1 ], no A[i + 1] [j - 1]. 

Recursive Solution:
Consider the DFS. Use post-order traversal, i.e. bottom-up traversal. 

Code (Java):

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        return postOrderTraversal(triangle, 0, 0);
    }
    
    private int postOrderTraversal(List<List<Integer>> triangle, int layer, int next) {
        if (layer == triangle.size()) return 0;
        
        int lMax = postOrderTraversal(triangle, layer + 1, next);
        int rMax = postOrderTraversal(triangle, layer + 1, next + 1);
        
        return Math.min(lMax, rMax) + triangle.get(layer).get(next);
    }
}

Discussion:
Now let's analyze the complexity. The time complexity is O(2^n) since it has many repeated calculations. Therefore we can think of a DP solution.

DP Solution:

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] dp = new int[triangle.size()][triangle.size()];
        return postOrderTraversal(triangle, 0, 0, dp);
    }
    
    private int postOrderTraversal(List<List<Integer>> triangle, int layer, int next, int[][] dp) {
        if (layer == triangle.size()) return 0;
        
        if (dp[layer][next] != 0) return dp[layer][next];
        
        int lMax = postOrderTraversal(triangle, layer + 1, next, dp);
        int rMax = postOrderTraversal(triangle, layer + 1, next + 1, dp);
        
        dp[layer][next] = Math.min(lMax, rMax) + triangle.get(layer).get(next);
        return dp[layer][next];
    }
}

Discussion:
From the solution, we can see that the space complexity now becomes O(n^2) since we allocated O(n^2) space of the array, where n is the number of rows. 

A Space-optimal Solution:
For the DP solution, we can find actually we only need to store layer i + 1 for calculating layer i. Consequently, we only need to create an array with size row (maximal number of numbers for the last row). 

Since DFS cannot traverse the "tree" in level order. In this solution, we use an iterative approach. 

Code (Java):

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.isEmpty()) return 0;
        
        int[] dp = new int[triangle.size()];
        
        // save the last row
        for (int i = 0; i < triangle.size(); i++) {
            dp[i] = triangle.get(triangle.size() - 1).get(i);
        }
        
        // start from the second last row bottom-up
        for (int i = triangle.size() - 2; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }
}

Summary:
This problem is a very classical DP problem. Make sure at least you understand the first recursive solution. The idea of post-order traversal is often used in many maximal/minimum path sum problems. Make sure you understand the first DP approach. The last solution is very tricky. Understand the idea.


Update on 10/9/2014:
Top-down 2D DP:
dp[i][j] -- the minimum path sum from root to position i, j
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
initial: dp[0][0] = 0;
dp[i][0] = dp[i - 1][0] + triangle[i][j];
Others are set to Integer.MAX_VALUE

Final state: min (dp[n - 1][0] ... dp[n - 1][n - 1])

public class Solution {
    int min = Integer.MAX_VALUE;
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        
        // 2D DP solution
        int n = triangle.size();
        int[][] dp = new int[n][n];
        
        // Initialize
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < triangle.get(i).size(); j++) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
            }
        }
        
        int min = Integer.MAX_VALUE;
        for (int i  = 0; i < n; i++) {
            if (dp[n - 1][i] < min) {
                min = dp[n - 1][i];
            }
        }
        
        return min;
    }
}

1D DP solution:
dp[j]: the minimum path sum from bottom to the column j at current level
Transit function: dp[j] = dp[j] + dp[j + 1]
Initial state:    Initialize dp[j] as the bottom number of the triangle
Final state:     dp[0].

Code (java):

public class Solution {
    int min = Integer.MAX_VALUE;
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        
        int n = triangle.size();
        /// 1D DP solution
        int[] dp = new int[n];
        
        /// Initialization
        for (int i = 0; i < n; i++) {
            dp[i] = triangle.get(n-1).get(i);
        }
        
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        
        return dp[0];
    }
}