问题 C[J] :以J为长度的钢条的最佳切割收益。
子结构:C[J]=MAX{P[J],C[J-I]+P[I]}
一个钢条的最佳收益:假设至多一刀,要么切,要么不切,遍历所有情况,找出最大的收益情况
(P[J];不切,C[J-I]+P[I] : 在I位置切一刀)
初始化:C[0]=0;
追踪:rect[J],以J为长度的钢条,记录切割位置;
(在网上找的图,N=N-记录的数字,算出右边的长度,为什么从右边?假如10要切成2和8
那么只会左边是2,右边是8,所以小的数字会在左边,大的在右边?(不知道对不对)
代码: