LeetCode Triangle: DP and Exactly N Extra Memory

Overview

Dynamic Programming (DP) could solve this LeetCode Triangle Problem elegantly with 10 lines of code. The space const an int array of size n and that’s it!

LeetCode Triangle 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

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

Dynamic Programming Approach

This one is a classical Dynamic Programming problem, if I am not mistaken, there is an exactly same problem in POJ. The dp formula is this: let dp[node] denote the minimum path sum of the tree rooted at “node”, then we have:

dp[node] = value[node] + min(dp[child1], dp[child2])

Simply run this dp and store all the value in an array, both time and space complexity would be O(N) where N is the total number of nodes in the tree. However, we could still save the space cost by just storing two arrays, one is the previous dp results and one is for the current dp results. The key observation is that to get the correct results, we only need the the immediate results of the children, all the lower level information is useless. More specifically, from the above formula, we could see, dp[node] value only depends on two levels information, the current level at node and the lower lever at its child. So we only need two arrays. And the maximum size of such array is at the bottom level with n nodes where n is the number of rows. So the EXTRA space cost would be O(2n) = O(n)  where n is the number of nodes in the bottom level and also is the total number of rows in the triangle.

Update: So based on previous analysis, two arrays are not necessary, only one is enough, it won’t be too hard to come up with the idea, so I will leave this to yourself to think about it more. Another diffierent top-down idea to tackle this LeetCode Triangle problem is treat dp[node] as the minimum sum from the root to the node, rather than treating node as the root, this approach treat node as th bottom “leaf node”. Actually various source code implementation could solve this problem, the following one is one of them accepted by LeetCode OJ to pass this Triangle problem:

int minimumTotal(vector<vector<int> > &triangle) {
    int n = triangle.size();
    if (n <= 0) return 0;
    int *dp1 = new int[n];
    int *dp2 = new int[n];
    dp1[0] = triangle[0][0];
    for (int i = 1; i < n; ++i) {
        dp2[0] = dp1[0] + triangle[i][0];
        dp2[i] = dp1[i - 1] + triangle[i][i];
        for (int j = i - 1; j > 0; --j) {
            dp2[j] = min(dp1[j], dp1[j - 1]) + triangle[i][j];
        }
        swap(dp1, dp2);
    }
    int ret = *min_element(dp1, dp1 + n);
    delete dp1, delete dp2;
    return ret;
}

Summary

Dynamic Programming (DP) could solve this LeetCode Triangle Problem elegantly with 10 lines of code. The space const an int array of size n and that’s it!

Written on January 26, 2013