Dynamic Programming (DP) Tutorial 0

Tutorial 0

Introduction to dynamic programming-

Agenda.

1.what is dynamic programming?

2.Type of dynamic programming

3.How to identify dynamic programming problem

4.parents problem of dynamic programming

 

1.Dynamic Programming or DP ?-

DP is a problem solving technique which can be divided into similar sub problem for more details

https://en.wikipedia.org/wiki/Dynamic_programming

 

Lets understand through an example-

There is a famous problem name as minimum coin change in this problem you have infinite supply of coins and you have to tell minimum coin change for x.

Coins=[1,5,6,9]

X=11

Now understand the concept of similar sub problem

Amount	0	1	2	3	4	5	6	7	8	9	10	11
Minimum coin change	0	1	2	3	4	1	1	2	3	1	2	2

 

For 0-0

For 1-1+remaining(1-1)=1+0=1 we can’t use coin 5,6,9 because it is greater than 1

We already assume that we have already find minimum coin change for smaller amount

For 2-

  1+remaining(2-1)=1+remaining price 1 and for price 1 minimum coin is 1=1+1=2

                           Here this one means 1 coin of value 1

For 5-

1 coin of 5+remaining 0=1+0=1

Or 1 coin of 1+remaining 4=1+4 because we already calculate for remaining price 4 =1+4

So minimum for 5=minimum(1,5)=1

For 11-

1 coin of 1+2=3      ||  1 coin of 6+1=2 || 1 coin of 5 +1   ||          1 coin of 9+2

so minimum is 2

now I think you understand the concept of similar sub -problem.

 

Type of Dynamic Programming-

1.Bottom UP or Tabular

2.Top Down or memorization

Don’t worry about Type as soon as we go forward you can easily understand this.

 

How to Identify Dynamic Programming problem-

Most of the people find difficulty here but don’t worry

1.Choice

2.Optimal

How to check choice?

In any problem if these two thing as that problem may be solve using dynamic programming

Now take these two thing on previous example minimum coin change

Here is choice for 5 either you can take the 5 coins of 1 or 1 coin of 5.

2.how  to check optimal –

If any problem ask  minimum or maximum lets take previous example

We have to find minimum coin change do you heard what I say minimum coin change.

 

Dynamic programming problems-

We have to not solve thousands of dynamic programming problem mostly problem are made on the concept of 10 parent dynamic programming problem.

Name of the problem	No. of child problem
1.0-1 knapsack	6
2.Unbounded knapsack	5
3.Fibonacci	7
4.Longest common sequence	15
5.Longest Increasing Sequence	10
6.Kadane’s algorithm	6
7.Matrix Multiplication	7
8.Dp on Tree	4
9.Dp on Grid	x
10.others	5

 

 

Why big Tech company asked problem related to dynamic programming-

Dynamic programming is a technique for solving a wide class of sequential decision-making problems under uncertainty so this problem enhance your decision making ability..