Dynamic Programming Guide

I’ve started with solving Dynamic Programming Questions in HackerRank, and its getting difficult for me to think dynamically, can I please get guide on how to think, dynamically?? I can do only those questions for which the approach I already know, like LIS and LCS, but apart from this, I couldn’t think and need to look at the solution.
P.s. I’ve already read the articles on DP from Topcoder DP, Cormen, DS and Algo by Narasimha Karimanchu…

No one other than you yourself can help you think Dynamically. Do more and more dynamic programming problems and a day will can when you will be able to think Dynamically.

**NOTE ::**To check whether the problem you are trying have dynamic programming solution see that if the problem could be break down into smaller sub problems which can be reused .

1 Like

I was also facing the same issue. What worked for me is practice. As previously mentioned by @coder_voder, just practice hard. As you have read necessary material already, now get your hands dirty :slight_smile:

1 Like

Dont worry! Try a problem (start with easy ones) for some time, think about each and every possibility which you can possibly apply. At last if you are not able to get to an appropriate logic, google it and read some solutions or post it in codechef forums. The next time u come across a DP question, you will definitely have a better idea of how to proceed, still if you are unable, repeat the process. Initially it might take you some time to think of the perfect logic since DP is quite a vast topic with thousands of varieties of questions. But once u have been familiar with the basic framework of how to proceed in questions based on DP, solving DP will be cakewalk for you.

You should start with 1-dimensional DP problems then move to some tougher ones like LCS or LIS. CodeForces has a good collection of DP problems and quite a good number of them are 1-dimensional. Thinking about the problem recursively is also intuitive (at least for me) so you don’t always have to solve them bottom-up! Think about the dp recurrence and state ( or the factors which govern the size of the dp problem ).

So I suggest you to start solving them and as others have said, practice is definitely the key to success!

Similar questions I found on Quora which may help : https://www.quora.com/I-am-unable-to-come-up-with-top-down-solutions-for-dp-problems-I-am-unable-to-think-recursively-What-should-I-do


1 Like

Thank you, That was helpful

Glad to know that :slight_smile: