本文共 628 字，大约阅读时间需要 2 分钟。

A log of wood has n marks on it. Cost of cutting wood at a particular mark is proportional to the length of the log. The log of wood can be cut at all the marks. Find the optimal order of the marks where the log should be cut in order to minimize the total cost of cutting.

--------------------------------------------------------------------------------------

Use dynamic programming. 
1) Add two auxilary marks on each end of the log (totally n+2 marks) 
2) min_cost[i][j]=minimum{min_cost[i][k] + min_cost[k][j] + length[i][j]}, where k=i+1 to j-1
3) min_cost[i][i+1]=0 
4) min_cost[i][i+2]=length[i][i+2] 
Find min_cost[0][n+1].

转载地址：http://uwboi.baihongyu.com/