问题3：如何思考？ 总存在最优方案，最优方案总有第一刀！ 第一刀切下去之后： 针对任意的r,我们能够写出下面的公式！ Tn=ri+rn-i 这个公式well define吗？ 最优子结构性质！ r+rn一定是rn吗？ 我们姑且放一放
rn : i rn =ri+rn-i 总存在最优方案，最优方案总有第一刀！ 第一刀切下去之后： 针对任意的rn，我们能够写出下面的公式！ 这个公式well define吗？ ri+rn-i一定是rn吗？ 最优子结构性质！ 我们姑且放一放
间题4：我们知道应该是多少吗？ In: Tn=ri+rn-i 从0开始遍历！ In max (Pn,1 Fn-1,2+In-2;...,In-1+1)
rn : i rn =ri+rn-i 从0开始遍历！
更关键的是：我们从公式中的求解中， 看到了什么？ In [n=ri+rn-i 递归！
rn : i rn =ri+rn-i 递归！
递归的解法：扫描所有可能的割法 In max (Pn,rI In-1,r2 +In-2,...,In-1+r1) max (Pi+rn-i) <i<刀 Cut-Rod(p,n){ P:价格表，n:长度 if n==0 return 0; q=-1; for(i=1 to n){ ∥递归遍历所有的“割法” q max(q,p[i]+Cut-Rod(p,n-i)) } return q;
递归的解法：扫描所有可能的割法 Cut-Rod(p,n) { //P:价格表，n:长度 if n==0 return 0; q=-1; for( i=1 to n) { //递归遍历所有的“割法” q = max(q, p[i]+Cut-Rod(p, n-i)) } return q; }
递归的解法： CUT-ROD(P,n) 当n=4时，递归调用树： 1 fn==0 2 return O 3q=-00 4 for i Iton q max(g.pli]+CUT-ROD(p,n-i)) 6 return q 问题5： 为什么这个算法注定是低效率的？
递归的解法： 当n=4时，递归调用树：