r/programming • • Apr 16 '19

A graphical introduction to dynamic programming

https://medium.com/@avik.das/a-graphical-introduction-to-dynamic-programming-2e981fa7ca2?source=friends_link&sk=37cd14642cf1a83eb0bb33d231442837
55 Upvotes

14 comments sorted by

8

u/bmcmbm Apr 16 '19

Gonna give it a read. I always understand simple problems solved with dynamic programming but fail to apply it to more complicated problems. It’s been 6 years since I was introduced to dynamic programming and it is still one of my weak spots when it comes to interview questions and coding competitions.

7

u/akdas Apr 17 '19

I agree with the other posters that seeing more problems is key. If there's interest, I'd be happy to write a follow up article with more examples.

4

u/RyanPointOh Apr 17 '19

Please do!

2

u/TheBestOpinion Apr 17 '19

You really should, I was going to say that this article was one of the best introductions to dynamic programming I've seen (I've looked for some last year as part of my studies)

3

u/carbonkid619 Apr 17 '19

I've found that dynamic programming is something you can only really get good at with practice, after a while all the problems start looking like ones you've encountered before.

3

u/DidiBear Apr 16 '19

Dynamic programming is just using memoization on recursive function then optimize memory usage

2

u/opiating Apr 17 '19

How does dynamic programming relate to the use of generators i.e. yield

1

u/akdas Apr 17 '19

Dynamic programming is a general technique for creating algorithms, whereas generators a tool you can use to implement algorithms. You can use both together in many ways.

For example, with the Fibonacci numbers I presented in the article, you may generate (yield) individual numbers in the sequence one by one. This would allow someone to consume these numbers sequentially, but to get to that point, you may use dynamic programming to generate the numbers in the first place.

1

u/wrensdad Apr 17 '19

Either I'm stupid or the article isn't friendly enough but I couldn't understand the logic behind the house robber one. Then it started jumping to math function notation `f(n-1)` before I knew what the robber was doing and I was out.

4

u/akdas Apr 17 '19

Sorry the article wasn't clear enough. I would love to clarify. The basic idea is that you work backwards from the last house to the first. At each house, you can:

  • Steal from the house, but then you have to skip the previous house (can't steal from two houses next to each other).

  • Not steal from the house, and then you don't have to skip the previous house. You might still skip the previous house, but stealing from that house is still an option should you choose to take it.

Does that intuition help?

3

u/skawid Apr 17 '19 edited Apr 17 '19

I struggled with this one as well; I figured out the recursive approach then couldn't figure out the next step.

For the recursive approach; Each house is a choice of rob and move two houses down, or move one house down. If there are no houses left the value is 0. If there's one house left the value is the value of that house. Otherwise, the value is the highest from: this house + all houses from two along; or all houses from one along. The code looks like:

def max_robbery(houses):
    if len(houses) is 0:
        return 0

    if len(houses) is 1:
        return houses[0]

    rob_current_house = houses[0] + max_robbery(houses[2:])
    leave_current_house = max_robbery(houses[1:])

    return max(rob_current_house, leave_current_house)


print max_robbery([3,10,3,1,2])

By printing the argument at every call to the function, I was able to build the tree similar to the one shown in the fibonacci demo. From that I got the dependency chain, I've roughed them up here. You can see where the duplicate effort is in the full tree, and how replacing them with arrows gives you a similar DAG to the fibonacci problem.

Now we know what lists we have to solve the problem for, in what order, we can start looking at them from the bottom up. Remember here, bottom up is from the end of the list backwards. The value in each case is the maximum the robber can rob.

  1. An empty list - has a value of 0.

  2. The value from the fifth house is that house's value - 2.

  3. The value from the fourth and fifth houses is whichever is highest - The value of the fourth house (1) plus the value of an empty list (which we figured out in step 1), or the value of the fifth house (which we figured out in step 2). This gives us 2.

  4. The value of the third, fourth, and fifth houses is whichever is highest - The value of the third house (3) plus the value from step 2, or the value from step 3. This gives us 5.

  5. The value of the second, third, fourth, and fifth houses is whichever is highest - The value of the second house (10) plus the value from step 3, or the value from step 4. This gives us 12.

  6. Finally, the value of all five houses is whichever is highest - The value of the first house (3) plus the value from step 4, or the value from step 5. This means we're still at 12.

Since we only need the values from the previous two steps, there's no need to keep everything. The code for the above sequence could be written as:

def dynamic_max_robbery(houses):
    # Start as value of empty list - step 1
    last_but_one_step = 0
    # Start as value of last house - step 2
    last_step = houses[-1]
    
    house_idx = len(houses) - 2
    
    while house_idx >= 0:
        new_step = max(houses[house_idx] + last_but_one_step, last_step)
        last_but_one_step = last_step
        last_step = new_step
        house_idx -= 1

    return new_step


print dynamic_max_robbery([3,10,3,1,2])

That's a tad awful. There are a couple of characteristics of this problem that make it possible to clean up to what was written in the blog:

The house order can be reversed without changing the outcome: [3,10,3,1,2] is the same as [2,1,3,10,3].

This gives us:

def dynamic_max_robbery(houses):
    # Start as value of empty list - step 1
    last_but_one_step = 0
    # Start as value of *first* house - step 2
    last_step = houses[0]
    
    for house in houses[1:]:
        new_step = max(house + last_but_one_step, last_step)
        last_but_one_step = last_step
        last_step = new_step
    
    return new_step


print dynamic_max_robbery([3,10,3,1,2])

The value of the first house can be found using the looping structure, giving you cleaner code at the expense of a few CPU cycles:

def dynamic_max_robbery(houses):
    # Start as value of empty list - step 1
    last_but_one_step = 0
    # Start as 0, but will quickly be set to value of *first* house - step 2
    last_step = 0
    
    for house in houses:
        new_step = max(house + last_but_one_step, last_step)
        last_but_one_step = last_step
        last_step = new_step
    
    return new_step


print dynamic_max_robbery([3,10,3,1,2])

From here, using some fancy python syntax to swap the values of the two previous steps in place gives us:

def dynamic_max_robbery(houses):
    # Start as value of empty list - step 1
    last_but_one_step = 0
    # Start as 0, but will quickly be set to value of *first* house - step 2
    last_step = 0
    
    for house in houses:
        last_but_one_step, last_step = last_step, max(house + last_but_one_step, last_step)
    
    return last_step


print dynamic_max_robbery([3,10,3,1,2])

Replacing last_but_one_step with a and last_step with b is left as an exercise for the reader.

1

u/akdas Apr 18 '19

Thanks so much for the insightful reply! Everyone has a different learning style, and I was trying to avoid focusing on the code for those who, like me, learn better from visuals.

However, the code is ultimately an important part of the puzzle, so I appreciate you sharing your perspective.

1

u/skawid Apr 18 '19

Cheers! Your description of the DAG helped me out - that's the bit I've been missing when I've looked at DP before. I just had an understanding gap between the robber problem and eventual solution, so it helped me to write it down as well.

2

u/zynasis Apr 17 '19

Great article. I still struggle to find use cases in my everyday work for DP, but perhaps that just takes more practice.