How one gets to know if one problem is a dp problem

#1

how one gets to know if one problem is a dp problem

#2

Hello @pragyachoudhary1111,

Here are the steps that I follow:

  1. Find a recursive solution to the problem

  2. At this point, I explore the recursion tree and see if there are overlapping sub-problems. This is a critical step in recognizing if the problem is dynamic programming or not.

  3. If there are overlapping sub-problems, then you simple memoize or cache the values.

At this point, I want to emphasize that there is no substitute for practice. Practising would help you in building a mental map about these patterns.

Hence, A problem can be solved using DP if it satisfies two properties:

  1. Overlapping Sub-structures: It refers to the problem when solutions of same subproblems are needed again and again. In dynamic programming, computed solutions to subproblems are stored in a table so that these don’t have to be recomputed. So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no point storing the solutions if they are not needed again.

  2. Optimal Subproblems: A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.

Hope, this would help.
Give a like, if you are satisfied.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.