Recently in many contests, i couldn’t solve all problems and after the contest : is it a DP problem??..
I have been quiet learning and practicing dynamic programming and I am a beginner in dp so I cant realize that when to use or solve a particular problem using dynamic programming. Hope someone helps and thanks in advance 
1 Like
That’s the same as asking “How do I know when to use this formula in maths/physics?” or “How can I solve any problem in the world?”. Thats the whole point of it 
It comes with practice and experience.
Right now, you could ask yourself a few Q-
- Any common sub-problem or overlapping structure?
- If i store the result for index i, can i somehow use it for any future operation?
For me 2. always works, because it helps me in my algorithm-thinking, and I get a clearer picture of how I may use previous results.
2 Likes
This stepwise thinking might not help when the problem demands some non-trivial dp. Being more creative sometimes helps.
Like in yesterday’s lunchtime problem, no way can you ask if you can store i’s result for future operation and then understand that it can be solved using dp.
All classic points have been mentioned by @vijju123 but at a quick glance you can check whether the input size permits a quadratic time algo if it permits then u can give a thought to dp else no. Yes but the dp has to be 2-D in order to check this
Consider the formula to be f = x * y.
Q. How do I know when to use this formula?
A. If you are given values of any two variables and are said to find the value of the remaining third variable, you can use this formula.
@ista2000, answer to this question exist. That’s the whole point of it
Practice and experience is not the only answer to every question. If you don’t want to help, at least try to respect the community members seeking for help. THATS THE WHOLE POINT OF IT. It comes with practice and experience 
Re-read my answer carefully. You missed the detail. I said “Right now”. OP said he is still beginner, so first thing is helping him become acquainted with dp. Once he solves easy ones on his own, he can take the next step and work on harder ones. Thats the perspective with which i helped him, hope i stand clear here
Thank you and it would be motivating for me if you could suggest where to start solving easy dp problems… and is it necessary to learn these basic dp problems inorder to get experience ?
Link: http://www.geeksforgeeks.org/dynamic-programming/#basic
this doesn’t apply for 1-d array dp ? how to choose 1D or 2D array like … I know it depends on the problem but is there a thought to analyze it in other way?
geeksforgeeks is fine. Easy dp Q, are actually a lot scattered 
There are some basic Q on which you should have full control over implementation, reasoning and thinking- like LIS, LCS, Max sum subarray. When you have a good command over them, you will be able to think through most of easy dp problems, which should give you confidence. Then you can proceed to the tougher ones.
Making a different answer because this didn’t fit the character limit 
Reply to @pratik_gadhiya (And also @vijju123 about the being a beginner):
Aah…you didn’t get it. I learnt this when preparing for the maths olympiad. We all learnt AM-GM inequality when in high school. I once was practicing from here( http://www.imomath.com/index.php?options=593&lmm=0 “Introduction to inequalities”, problem 13 ). I was stuck and wanted a teacher to help me out. I asked my teacher she gave me a lecture on Muirhead, Jensen and what not. I came back, saw the solution and all it was was simple AM-GM. Even if you know AM-GM, it wasn’t that obvious. I really enjoyed solving it
By “That’s the whole point of it”, I meant thats the whole point of programming competitively(problem solving). If just knowing the formula would help you solve any problem based on that formula, then there would be no tourist and there would be no ista2000. Thing is, every problem requires you to use something you know in some different way.
Think about it in this way. The first person to ever think about DP ever. Did he know that he has to think about how to use the answer for i to find answer for i+1 and work it out? Thinking like this when learning(Especially when you are a beginner) hampers your learning curve later.
Look at yesterday’s lunchtime problem(Second one). I really enjoyed solving it. There was no way for you to think about it in a classical way(Unless you know SOS DP Hardcore of course) and come up with a solution.
And yes, practice and experience IS the answer to every question(Except if its a problem specific question, haha). Lets see who disagrees.
Now if you say,“Why listen to this 4 star who has not accomplished anything?” Don’t, not asking you to listen to me, at least argue with me, I am open to discussions.
Think about it in this way. The first person to ever think about DP ever. Did he know that he has to think about how to use the answer for i to find answer for i+1 and work it out? Thinking like this when learning(Especially when you are a beginner) hampers your learning curve later.
You dont teach swimming by throwing somebody in an ocean. Those people arent clueless when they teach you beginner dp with examples of fibonacci number and what not. He will drown. We start from basics, give a foundation and when that person gets basic skills, he will be able to do it.
1 Like
just saying, star rating does not matter
Its what i said earlier, different methods work for different people. Just because it worked for you doesnt mean it will work for him, and vice versa. Its upto him to choose his way, we can only highlight the method how we did it.
Haha, codeforces does matter tho, I am a green 
Your answer assumes that the coder thinks about DP in a bottom-up manner. Why not think about DP like this: “How can I find the answer for i using the answer for all the indexes that precede it?” I am saying that there should be a general principle that applies to everything instead of restricting someone’s viewpoints to some specific way of thinking.
Well, I wrote that because i HAD to give some example, no? Also, i wrote
If i store the result for index i, can i somehow use it for any future operation?
Arent you assuming that by future operation i only mean bottom up manner?
It was general enough. If result for index i is stored, will it help in any future operation?
“Its what i said earlier, different methods work for different people. Just because it worked for you doesnt mean it will work for him, and vice versa.”
Thats the thing, I am not mentioning any specific method, I am giving a general approach.
Look at the way I asked the same question, only top down.
And btw, vijju, mind accepting my friend request on fb? Have sent you long ago, my ego gets hurt this way tho.
1 Like