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

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!

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

Thank You very very much!