DP solution to min triangle path

I am studying for interviews for various companies. I wrote a solution to this problem, but if an experience programmer looks at it I am sure there are certain areas the code can be made in to a more beautiful code.


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

My DP solution:

public class Solution {
public static int minimumTotal(List> triangle) {
        if(triangle==null){
            return -1;
        }
        int [][] dp=new int[triangle.size()][triangle.size()];
        for(int i=0;i> tri, int level, int index, int [][]dp){
        if((level+1)==tri.size()){
            dp[level][index]=tri.get(level).get(index);
            return dp[level][index];
        }else{
            int left=-1;
            int right=-1;
            if(dp[level+1][index]!=0){
                left=dp[level+1][index];
            }else{
                left=getMin(tri, level+1, index,dp);
            }
            if(dp[level+1][index+1]!=0){
                right=dp[level+1][index+1];
            }else{
                right=getMin(tri, level+1, index+1,dp);
            }
            dp[level][index]=tri.get(level).get(index)+Math.min(left,right);

            return dp[level][index];
        }
    }
}

Code Style

Although not the most important aspect of programming, I'd recommend using a bit more spaces in your code.

Just a few random example lines:

dp[level][index]=tri.get(level).get(index);
if(dp[level+1][index+1]!=0){
    right=dp[level+1][index+1];
dp[level][index]=tri.get(level).get(index)+Math.min(left,right);

(Note that these four lines do not belong together in the original code)

These would look better as:

dp[level][index] = tri.get(level).get(index);
if (dp[level + 1][index + 1] != 0) {
    right = dp[level + 1][index + 1];
dp[level][index] = tri.get(level).get(index) + Math.min(left, right);

This does improve readability quite a bit, and is the Java conventions.

Exceptions for exceptional cases

if(triangle==null){
    return -1;
}

Instead of returning the special value -1 here, which could be a valid output if your input contained some negative numbers, it is better to throw an exception.

if (triangle == null) {
    throw new NullPointerException("triangle cannot be null");
}

Or, using a Java method call as of Java 7:

Objects.requireNonNull(triangle, "triangle cannot be null");

Last index

When checking if an index is the last index in a list:

if((level+1)==tri.size()){

Then it is more common to compare the actual index, rather than the size:

if (level == tri.size() - 1) {

And as you see, you can remove one set of parameters as well.

Initialization

As all int-arrays are initialized to zero by default, this code does absolutely nothing:

for (int i = 0; i < triangle.size(); i++) {
    Arrays.fill(dp[i], 0);
}

Working backwards

Sometimes when faced with a challenge, it can be a good idea to think: What if I work backwards? Sometimes working from the other direction can be a big advantage. A different approach to this problem would be to work backwards.

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

Start at the bottom row. On this row, we can find that the 8 is irrelevant as it is right in the middle of two much smaller numbers that can be reached instead, from the same parents that can reach the 8. The same way, we can see that the 4 is a much worse choice than the 1. So the information we want from that row is [, 1, , 3].

Now on to the next row! [6, 5, 7]. We find out that the 6 is totally irrelevant as the 5 can also be reached from the same parent (the 3 above). Additionally, the only child of 5 is 1, but the child of 7 is 3. As 1 + 5 < 3 + 7, 1 + 5 does seem like a better route so far. But to be safe, I would store the sum for each of the current 'nodes'. So for the 5, store 1 + 5 = 6. For the 7, store 3 + 7 = 10.

On to the next row! [3, 4]. Here we can find out that the 3 is much better, as the only way the 4 is relevant is because 3 + 7 = 10. But as 1 + 5 + 3 = 9 is smaller than 3 + 7 + 4 = 14, and the 3 and 4 are neighbors, we can totally forget about the 3 + 7 + 4 = 14 path, as it is now irrelevant thanks to our superior 1 + 5 + 3 = 9 path.

Last row, [2]. Here we don't have any choice, so we just add the 2 to our current 1 + 7 + 3 = 9 path and we end up with 11.

Edit: after some debugging of your code, your approach is actually quite fast and very similar to what I started doing here. We just don't use the same order when iterating over the triangle. But if you want to see what I ended up with, take a look at my question.

The fact that I thought your code was slower than it actually was might be an indication about the readability of your code. I think that by getting rid of the recursion the way I did the actual algorithm used is more apparent, and thus it is more clear that the time complexity is not \$O(2^n)\$ which it looks like at first glance.

StackExchange Code Review Q#67121, answer score: 5