Hey there and welcome back!
In this video, let's discuss how can one identify whether a particular coding interview problem statement
can be solved using dynamic programming or not?
Now to identify this, the first indicator is that if you are asked to find an optimal solution.
It would probably mean that you can solve the question using dynamic programming.
Now what do we mean with an optimal solution?
These are things like the longest or the maximum of something, or the minimum of something, etc. so
if the question asks you to find an optimal solution, remember you probably can solve it using dynamic
programming.
The next hint that you can take to decide whether a problem can be solved with dynamic programming or
not is by checking whether the problem involves recursion or choices.
Now, if there are choices in the problem, then probably you can solve it with recursion, and especially
if the choices are such that there are multiple branches, something like this, where you have two
or more paths, then there is a high probability for overlapping subproblems.
And remember we had discussed that you can use DP when the problem is such that you have overlapping
subproblems and optimal substructure.
So these are two hints that you can use to identify whether a problem can be solved using dynamic programming
or not.