How to understand if a problem can be solved with DP or not?

1

Hello people,
I am new to this platform.
I have been learning dynamic programming lately, solved few problems from GeeksForGeeks, possibly start solving on CC.
But here, the question is, how would I know if a problem can be solved using DP?
Like for example, if someone asks me to code a program which would generate a Fibonacci series, I can write both the recursive as well as iterative approach.

Sorry, if my question seems to be too much obvious or naive, I am a beginner.
Thank You!

2

Dynamic Programming is Optimized Recursion. To be good in DP you should have strong knowledge of Recursion.

Moving Further There are some things you can notice to find out if a problem requires DP solution or not.

  • If problem is related with choosing combinations to get optimal output.
    Optimal here means MAX or MIN.
  • If there is a recursive solution possible to some problem then to have a DP solution check if the recursive function is repeating over sub-problems or not. This could be done by simply creating a recursion tree.
  • Most Dynamic Problem solutions are O(n^2) so you can also check if DP is feasible or not by looking the constraints however it’s something i won’t prefer.
  • Never start with a top-down(Tabulation) approach unless you are sure of how to create the table.
  • Try to think of a recursive Solution first then try to use Memoization(bottom-up) (which is also DP) . If memoization fails due to some stack overflow which could occur in rare cases then go for top-down approach. Mostly To convert a Bottom-UP into Top-Down, Breaking condition of Bottom-up recursion becomes the initialization of Top-Down DP and rest is changed accordingly. The Point is that if you can come up with a Bottom-UP solution then You can always create it into a Top-down DP.
2 Likes
3

Thank You very very much!