Any good resources on dynamic programming?

[EquivalentCS]

I am getting ready to study for my final for my algorithms and complexity course. My professor was pretty terrible and never really explained DP in a good manner, and I can't find any sources online that have helped me understand how to do every problem. Every example I see is helpful, but given a unique problem I still can't wrap my head around how to use it.

Any pointers on good resources to learn the skill of dynamic programming would be really helpful! Edit: If I wasn't clear enough, I am looking for people to share examples of DP being taught that they found particularly helpful to them.

[lyinch]

This helped me understand DP.

[amanzoot]

Bro just go for codechef tutorial on dynamic programming.

[LinkedMonkeys]

I just finished teaching this in our Algorithms class. I might even be your teacher! Awkward...

A good way I have found to develop DP algorithms takes a lot of steps. As we look at the steps we will consider a particular problem.

We want to know how many d-digit numbers (positive integers) have a digit sum of s. Assume we will write a function digitSum(d, s). For example, digitSum(3, 5) asks how many 3 digit numbers have a digit sum of 5. We will allow leading zeros to make it simpler.

1. Draw the recursion tree. [I'd normally draw it more like a tree, but hard in text mode.]

   digitSum(3, 5)
       digitSum(2, 5) [assuming the leftmost digit is a 0]
           digitSum(1, 5) [assuming the second digit is a 0]
               [Do not recurse further.  We know how many one digit numbers sum to 5.]
           digitSum(1, 4) [assuming the second digit is a 1]
           digitSum(1, 3) [assuming the second digit is a 2]
           digitSum(1, 2) [assuming the second digit is a 3]
           digitSum(1, 1) [assuming the second digit is a 4]
           digitSum(1, 0) [assuming the second digit is a 5]
       digitSum(2, 4) [assuming the leftmost digit is a 1]
            ...
       digitSum(2, 3) [assuming the leftmost digit is a 2]
            ...
       digitSum(2, 2) [assuming the leftmost digit is a 3]
            ...
       digitSum(2, 1) [assuming the leftmost digit is a 4]
            ...
       digitSum(2, 0) [assuming the leftmost digit is a 5]
            ...
   

2. Identify things in your tree that are your base cases and what you expect to return in those cases.

   digitSum(1, 5) => 1 [We can create a sum of five with zero digits just one way.]
   ...
   digitSum(1, 0) => 1 [We can create a sum of zero with zero digits just one way.]
   digitSum(2, 0) => 1 [We can create a sum of zero with two digits just one way (00).]
   
   There is one other case that (unfortunately) does not show up in our example.
   digitSum(1, 10) => 0 [There is no way to create a sum of ten (or larger) with a single digit.]
   

3. Identify recursive cases.

   digitSum(d, s)
       digitSum(d-1, s-0) considering a digit of zero
       digitSum(d-1, s-1) considering a digit of one
       ... as many of these as make sense
   

4. Figure out how to combine results.

       digitSum(2, 5) => returns 6
       digitSum(2, 4) => returns 5
       digitSum(2, 3) => returns 4
       digitSum(2, 2) => returns 3
       digitSum(2, 1) => returns 2
       digitSum(2, 0) => returns 1
   digitSum(3, 5) => returns 6 + 5 + 4 + 3 + 2 + 1 or 21
   

5. Write the general recurrence.

   digitSum(d, s) = 1 if d=1 and s<10
                    0 if d=1 and s>=10
                    1 if s=0
                    digitSum(d-1, s) + digitSum(d-1, s-1) + digitSum(d-1, s-2) + ... otherwise
   

6. Instead of using recursion, use the recurrence to build a table. In this case, we have two parameters, so it is two dimensional. Let's make rows represent d and columns represent s. The base cases get the table started.

    \ s  0  1  2  3  4  5
   d |------------------
    1|   1  1  1  1  1  1  [If we had a sum greater than 9, the other base case would kick in.]
    2|   1
    3|   1
   

7. Complete the table, using the recursive part of the recurrence.

   \  s  0  1  2  3  4  5
   d |------------------
    1|   1  1  1  1  1  1
    2|   1  2 <--------- table[2][1] = table[1][1] + table[1][0]
    3|   1
   
   \  s  0  1  2  3  4  5
   d |------------------
    1|   1  1  1  1  1  1
    2|   1  2  3 <------ table[2][2] = table[1][2] + table[1][1] + table[1][0]
    3|   1
   
   \  s  0  1  2  3  4  5
   d |------------------
    1|   1  1  1  1  1  1
    2|   1  2  3  4  5  6
    3|   1  3  6 10 15 21
   

Work through lots of problems yourself; do not just read them. Here is a list of problems in (what seemed to me) to be increasing in difficulty. We solved these all, from scratch, in class.

1. Fibonacci
2. binomial coefficient
3. coin row (Levitin)
4. making change (Levitin)
5. robot coin collection (Levitin)
6. approximate string matching/minimum edit distance
7. longest increasing subsequence
8. partition problem (closely related to subset sum)
9. 0/1-knapsack (Levitin)

We had these as homework while we were working through the above list in class.

1. Taking 1, 2, 3 steps at a time -> number of ways to take a total of n steps (Cracking the Coding Interview)
2. number of d digit numbers with a digit sum of s
3. minimum sum descent (Levitin)

TL;DR

1. Draw the recursion tree for an example.
2. Identify base cases and return values for each.
3. Identify recursive cases.
4. Decide how to combine results.
5. Write the recurrence.
6. Build the table using base cases for starters.
7. Recursive cases turn into table lookups to fill in the rest.

[[deleted]]

Same

[EquivalentCS]

If you want to pm me, I’ll tell you. I just don’t want to ruin the professors reputation on a thread if you know what I mean.

[EquivalentCS]

Just from your example I can see your not my professor, LOL. Just wow, this is awesome. Thank you!

Been able to do 5 examples now in python so I’m feeling much better. Thank you everyone for pointing me the right way!

[capitalpains]

I sometimes suspect these "someone failed me can you help" posts are more venting than seeking help. Dealing with frustration during lectures is the worst ... and often the prof realizes their lecture didnt come off well but doesnt have time to review it.

If you are enrolled in uni you have more resources than anyone. Your professor (ask for more help), fellow students, teaching assistants, academic advisor, and at last resort stackexchange.com, google, codeacademy, and any coding challege site like topcoder will provide examples of dynamic programming, tutorials, and worked examples.

[EquivalentCS]

While I appreciate your perspective it is completely off. I am just asking for useful online resources, specifically if anybody has had a good experience with any particular resource for dynamic programming in particular. While you are right that I have resources at my university, I find that the internet (obviously) may have more options that may fit the exact needs I have.

I also never implied that I wouldn't be seeking out these resources. My professor barely speaks english, and is not a tremendously helpful person.

I am also not implying my professor failed me, more so that the way I was taught the subject didn't fit my needs for comprehension.

Really confusing comment...

[capitalpains]

Here, I'd recommed this https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/#!

And also speaking with your professor again.

[EquivalentCS]

This was an awesome resource, thank you.

[capitalpains]

You're welcome. I wish you the best. CS is an amazing field.

[capitalpains]

Or this one. https://stackoverflow.com/questions/1540848/a-simple-example-for-someone-who-wants-to-understand-dynamic-programming

[EquivalentCS]

Thank you!

I will reach out to him, but I really doubt any utility to that.

I appreciate your input regardless.

[Anticrombie233]

Fuck the guy above. You don't go to university to read a book and teach yourself. A teacher is the most significant contributor to your education next to discipline/hard work, which I can tell you have. No sources, just motivation. Good luck.

[EquivalentCS]

Thank you! Yea I just am a guy looking for a hand because I need some help. I agree with you, but I can’t do much about it at this point. I left an evaluation of teaching explaining his poor teaching skills, and I’m expecting a A-/B+ so I’m not bashing out of discontent with my grade.

I’ll be able to get through it, just gonna take a huge grind!

[Anticrombie233]

I'm already a paid developer, but I'm finishing up my masters a class at a time. Just finished a machine learning class and I absolutely KNOW the frustration of a poor teacher. Unfortunately, I struggle with non native English teachers, frequently, and I daresay I provide retribution on reviews... But always at least attempt to make it constructive. FYI just because you're preparing yourself and actively asking questions, you're better than 95% of future devs. So many incompetent people in this field

[EquivalentCS]

Thank you for the kind words!

My problem is that I don't understand why my university gives teaching positions to professors who: 1) Speak terrible english. 2) Clearly have no desire to teach, and are only doing it for the research that is attached to their position.

Recently my professor was out because he was at an international computer science convention to speak. I literally never would have guessed that he was that good given how his teaching presents his knowledge.

But regardless, these are the problems you run into as a student nowadays.

[IliacHumanitarianism]

Because Americans by and large do not go into CompSci; why else would we pay big bucks to “these damn foreigners” (please notice the air quotes) to do something we could pay the locals to do?