You are not logged in. Please login at www.codechef.com to post your questions!

×

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..

asked 24 Dec '16, 02:02

neilit1992's gravatar image

3★neilit1992
1.1k13
accept rate: 20%


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

https://www.quora.com/Why-do-I-suck-at-programming-dynamic-programming-algorithms-in-particular

link

answered 24 Dec '16, 15:42

nikhil_chandak's gravatar image

5★nikhil_chandak
3712
accept rate: 23%

Thank you, That was helpful

(24 Dec '16, 18:37) neilit19923★

Glad to know that :)

(24 Dec '16, 18:46) nikhil_chandak5★

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 .

link

answered 24 Dec '16, 06:26

coder_voder's gravatar image

2★coder_voder
593332
accept rate: 8%

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 :)

link

answered 24 Dec '16, 12:17

manishsingla's gravatar image

2★manishsingla
413
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,211

question asked: 24 Dec '16, 02:02

question was seen: 1,113 times

last updated: 24 Dec '16, 18:46