CODEWITHSUNDEEP
c++cdynamic-programming
Ankit
Ankit

Reputation: 361

Dynamic Programming Problem

I am just unable to get the hang of dp. I know what I've to do but am just unable to implement it.E.g this practice problem from 'Codechef'

http://www.codechef.com/problems/MIXTURES/

If i consider the min smoke for mixtures i to j as m[i,j]

then 

for k<- i to j 
m[i,j]=min(m[i,k]+m[k+1,j]+cost of mixing the resulting mixtures)

Is this correct? and how do I keep updating the colors of the mixtures for diff k and then revert back to original for the next k?

Upvotes: 5

Views: 1420

Answers (1)

deinst
deinst

Reputation: 18772

Yes, you are on the right track.

The color of m[i,j] does not depend on the order of the mixtures.

Upvotes: 3

Related Questions