Help with learning DP

Hello all,

I’m finding it very difficult to do DP problems. I read the Cormen chapter on DP, even the Topcoder algo tutorial and various Quora answers related to DP by some awesome people. I understand the theory but in doing problems I’m facing difficulty. Please suggest me the right approach for practicing DP.

Thanks in advance.

Practice, practice and more practice.

In my opinion DP is the most strange approach in programming. You just need trying to solve problems. In codeforces problemset you can filter all problems using DP. So try solve one. If you fail, you can find tutorial to it and learn right approach. And continue. Firstly is hard even to see, that solution will use DP, after some time, you will see pattern :slight_smile:

But I try give you some advice how to access such problems. In DP all is about right question. What I want to count and from which values I can count it? So try asking many such questions. The next thing is look at it in reverse. Because DP can be almost everytime be converted to recursion with memoization and vice versa. So you can ask not “What can I build from smaller states.” but “How can I divide large state to smaller ones.”. Personaly I prefer this approach.

6 Likes

Thankyou, michal27. :slight_smile:

1 Like

you’re welcome :slight_smile:

@michal27 where are u these days ??