c++ - 动态规划问题

Question

我只是无法掌握dp。我知道我要做什么，但无法实现它。例如，来自“Codechef”的这个练习问题

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

如果我认为混合物 i 到 j 的最小烟雾为 m[i,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

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

m[i,j] 的颜色不取决于混合物的顺序。