1
00:00:00,170 --> 00:00:02,180
Hey there and welcome back!

2
00:00:02,480 --> 00:00:10,130
In this video, let's discuss how can one identify whether a particular coding interview problem statement

3
00:00:10,130 --> 00:00:13,820
can be solved using dynamic programming or not?

4
00:00:13,850 --> 00:00:22,040
Now to identify this, the first indicator is that if you are asked to find an optimal solution.

5
00:00:23,020 --> 00:00:28,150
It would probably mean that you can solve the question using dynamic programming.

6
00:00:28,150 --> 00:00:31,540
Now what do we mean with an optimal solution?

7
00:00:31,540 --> 00:00:38,020
These are things like the longest or the maximum of something, or the minimum of something, etc. so

8
00:00:38,020 --> 00:00:46,180
if the question asks you to find an optimal solution, remember you probably can solve it using dynamic

9
00:00:46,180 --> 00:00:46,900
programming.

10
00:00:46,900 --> 00:00:54,400
The next hint that you can take to decide whether a problem can be solved with dynamic programming or

11
00:00:54,400 --> 00:00:59,500
not is by checking whether the problem involves recursion or choices.

12
00:00:59,500 --> 00:01:06,220
Now, if there are choices in the problem, then probably you can solve it with recursion, and especially

13
00:01:06,220 --> 00:01:13,210
if the choices are such that there are multiple branches, something like this, where you have two

14
00:01:13,210 --> 00:01:18,910
or more paths, then there is a high probability for overlapping subproblems.

15
00:01:18,910 --> 00:01:25,090
And remember we had discussed that you can use DP when the problem is such that you have overlapping

16
00:01:25,090 --> 00:01:27,700
subproblems and optimal substructure.

17
00:01:27,700 --> 00:01:35,110
So these are two hints that you can use to identify whether a problem can be solved using dynamic programming

18
00:01:35,110 --> 00:01:35,830
or not.