CODEWITHSUNDEEP
javadynamic-programming
EI-01
EI-01

Reputation: 1095

Trouble understanding dynamic programming

I came across this 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. 

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

This is an example of dynamic programming. But a very difficult or confusing concept for me when i come an exercise. I have watched videos and read tutorials online and it seems pretty easy at first but when i approach a problem then i'm totally lost. So i found a solution online and that uses a bottom approach:

public init minmumTotal(ArrayList<ArrayList<Integer>> triangle) {
       if (triangle.size() == 0 || triangle == null)
                   return 0;
     int[] dp = new int[triangle.size()+1]; // store each index’s total
       for (int i = triangle.size()-1; i >=0; i--) {
             for (int j = 0; j < triangle.get(i).size(); j++) {
                // first round: dp[j], dp[j+1] are both 0
               dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j); 
             }
         }
             return dp[0];
         }

Seems easy after going through the solution. But can this be done using a top down approach? And could someone explain why the bottom approach is better than the top down approach? Also when is it appropriate to use either top down or bottom up? And also since the question mentioned that each "Each step you may move to adjacent numbers on the row below." Does that mean for each row iterate the whole column before i step into the next row?

Upvotes: 1

Views: 209

Answers (2)

Mark
Mark

Reputation: 1498

A little off topic but the first if-statement in that solution needs to be turned around if you really want to handle NullPointerExceptions the right way.

So I tried myself at a top down approach and there are a couple of problems.

First, like marstran already said, you have more numbers in the end and need to do a minimum search.

Second, the bottom up approach used an additional array field to make sure it wouldn't run into IndexOutOfBound Exceptions. I didn't really find a good way to do that in top down (the bottom up approach has the advantage that you always know you have two numbers to look at (left child and right child) with the top down approach a lot of nodes don't have a right or left parent). So there's a couple of additional if-statements.

public static int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
    if (triangle == null || triangle.isEmpty()) return 0;

    int[] results = new int[triangle.size()];   

    for (int i = 0; i < triangle.size(); i++) {
        ArrayList<Integer> line = triangle.get(i);

        for (int j = line.size() - 1; j >= 0; j--) {
            if (j == 0) results[j] = line.get(j) + results[j];
            else if (j >= i) results[j] = line.get(j) + results[j - 1];
            else results[j] = line.get(j) + Math.min(results[j], results[j - 1]);
        }
    }

    int minimum = results[0];
    for (int i = 1; i < results.length; i++) {
        if (results[i] < minimum) {
            minimum = results[i];
        }
    }

    return minimum;
}

Anyway this is as close to the given solution as I could get with a top down approach.

Keep in mind though that nobody is forcing you to only use a 1d array for your results. If that concept is too difficult to just come up with, you could simply use a 2d array. It will increase the amount of code you need to write, but maybe be a little easier to come up with.

Upvotes: 0

marstran
marstran

Reputation: 27971

I'm not sure if this solution counts as dynamic programming, but I think it is very efficient.

You can start at the bottom of the triangle, and then collapse it by moving upwards in the triangle. For each number in the next row, add the lowest number of the two numbers below it. When you get to the top, you will only have one number, which would be your result. So you would get this:

Start:

   2
  3 4
 6 5 7
4 1 8 3

Step 1:

   2
  3 4
 7 6 10

Step 2:

   2
  9 10

Step 3:

   11

Upvotes: 2

Related Questions