动态规划问题

Question

我就是不能掌握dp的诀窍。我知道我必须做什么，但就是无法实现它。例如，这个来自“Codechef”的练习题。

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

如果我考虑混合物i到j的最小烟雾为mi，j

然后

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

这是正确的吗？我如何不断更新diff k的混合颜色，然后恢复到下一个k的原始颜色？

Answer 1

是的，你在正确的轨道上。

mi，j的颜色不依赖于混合物的顺序。