dynamic programming

Question

To be considered as a dynamic programming model...there are 2 properties

1.must have optimal substructure

2.must have overlapping subproblems

Only if both  are satisfied it is dynamic or any one if satisfied is sufficient

Comments

both should be simultaneoulsy satisfied for a problem to be able to apply DP approach,

if only 1) is satisfied but not 2), it will just become divide and conquer..

if only 2) is satisfied but not 1), there will no way to decompose higher order problem to smaller ones...

---

@joshi

Then look at this one

https://gateoverflow.in/2127/gate2011-25

Where is this problem having overlapping solutions?

How is it DP approach

---

here, it is having overlapping subproblems..

Li={1 + L_i+1, if A[i] < A[i+1]

         1          ,Otherwise }

Finally the the length of the longest monotonically increasing sequence is Max(L0,L1,…,Ln−1).

 suppose, you have to compute L5 at a particular moment, for that you have to recurse like this

 L5->L4->L3->L2->L1,

now, L4, L3, L2 all are overlapping subproblems, which you would have already computed in previous steps and stored them in some array. now,

since you have computed and stored the value of L4 in some previous steps, you can directly use it in L5 without following recursive call, it will look like

L5->A[L4] // here Array A is storing computed value of L4..

---

@joshi

here there is a case that suppose from starting we encounter an increasing sequence of lenth 3...it then breaks...then after some inputs we agan encounter an increasing sequence which goes upto length 6

now we traverse back to find the max

leads to overlapping subproblems and therefore dynamic

if the question was we have to find the longest incresing sequence from start

then it will not be a dynamic approach right....becz we just keep incerementing a count variable if it is in increasing sequence and when it breaks...just display count

have i understood it correct

---

yupes...correct..