"Dynamic programming"-What one should know

As the heading states I wanted to ask “what are the things one should know before starting dynamic programming?”.
That includes

  • Functions
  • algorithms
  • techniques

Thank you, I already googled the questions but I only found to topic “related” to it and none stated what you should know, so I request you to explain what are the things one should know before beginning to study dynamic programming.(Note:I am not asking what dynamic programming is but my question is what are function one should know before studying the topic.)

Before dynamic programming you should know how ‘Recursion’ works. Then it’s all practice and practice. There are some classic DP problems like knapsack, coin change, LCS - you should start learning them one by one. You will learn by solving different problems.

1 Like

Hey @monsterguy,

To start with Dynamic programming you must first know how the backtracking/ recursion works exactly.You can also say that it is a pre-requisite of learning dp. After that, i think you need to learn how to find the state of dp. Rest all is practice.

Resources - Topcoder

Hope this helps!

1 Like

Is recursion all one needs to know, I was asking about functions like ‘linked list’ etc.

@monsterguy dynamic programming is a very general approach and in different scenarios you may (or may not) require different additional algorithms as subprocedures, however the concept of recursion forms the basis of dynamic programming and is applicable to all dp problems.
And as @sandeep_007 said, the rest is all practice :slight_smile:

Okay, thank you.

There are different tutorials available for DP to start from scratch… I found some on different platforms which may help…

CodeChef, HackerEarth, TopCoder Same as sandeep_007 mentioned, Some link Found through CodeForces. There are plenty of articles and suggestions like this on net, on Quora and on different coding platforms.

You should try to think, how can you solve smaller problem if given and from that how can you solve problem just bigger than this. Try to think in different dimensions, like the problem from this August challenge CHEFFA. By practicing in proper order you will learn how can you choose different dimensions of problem to break it into simpler problem which will help to solve bigger problem using iteration or recursion. It can be combined with other concepts too but that would be later part.

For Practicing in proper order I will suggest to try codeforces problem in order of solved by most people here. This was point from where I started and learnt many things after that.

Hope this will help.

1 Like