Do all DP problems have a recursive solution?

#1

This query is related to approach a question of DP.
Is it that I should first try to come up with a recursive solution? And then do memoization?
And, Do all DP problems have a recursive solution?
And is it easier to think recursively first?

#2

Do we always have a recurrence relation to be found out to solve a DP problem?

#3

Hy @sagnik.pal2017
It’s generally observed that every DP problem has a recurrence relation but it’s not always true. There can be problems with not a pretty defined recurrence relation but still coming under Dynamic programming paradigm and even sometime recurrence relation are so hard to crack that solution without considering them works fine. The best way to find a DP problem is to look for overlapping subproblems and optimal substructure. Having a recurrence relation or not, will not help you everytime but Yes it’s recommended that try to find a recurrence first.

Thanks and Regards
Sanket Singh

1 Like
#4

If I am not able to think of the recursive solution, how will I justify that there are overlapping sub-problems?

#5

@sagnik.pal2017 you need a lot of practice in this topic if the subproblem of a problem is repeated again and again and you have to calculate every time this situation called as an overlapping sub-problems
for eg
we want to calculate nth Fibonacci no

as you can see on the left subtree f(4),f(2)…f(0) and right subtree f(4),f(2)…f(0) again being calculated again and again this will increase the complexity to exponential time o(2^n) which is very high
so resolve this problem dp will be used
there are two types of dp used top-down dynamic programming which is also known as memoization
in which you store you result in the data structure like an array so that you don’t have to calculate for subproblem again and again. If the result present in the array then the result will return from the array
and another method is used bottom-up dynamic programming in which you build your result from the bottom-up manner

1 Like