how to differentiate between a normal problem and where to use dp.please help.
1 Like
When you observe that the answer up to a point, can be used to easily or quickly find the answer up to the next point, you should consider DP.
Always ask, what is important up to THIS Point? If you see that the answer to the current state only depends on the answers to the previous states (Preferably last few), then you can almost always use Dynamic Programming.
Sometimes, if the problem is a 2D DP, it’s even easier to recognize as the constraints would be implying an O(NM) solution.
I suggest you to refer to Errichto’s DP Tutorials on the youtube.
It’ll come with experience. Solve a lot of questions. Try AtCoder DP Problems. Errichto has also made a Solution Video for these problems, so if you’re stuck, you can always learn from his thought process and continue.
2 Likes