南京大学：《计算机问题求解》课程教学资源（课件讲稿）动态规划

计算机问题求解一论题3-1 动态规划 2016年08月31日

计算机问题求解 – 论题3-1 - 动态规划 2016 年08 月31 日

Fibonacci:F=F+Fn2 问题1： 如果要你计算第n个 Fibonacci数，你用递归还是 用循环，还是随便？为什么？

递归可能代价高昂 计算第n个Fibonacci数 其实可以在线性时间内 - (以加法次数计量)完成。 6 18 23 3 3 16 24 25 21 10 但如果采用递归，递归 调用的次数是2Fn+1~1

递归可能代价高昂 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 2 4 3 3 3 6 5 4 13 16 10 11 9 8 12 3 4 5 6 7 14 15 21 2 1 19 18 17 25 23 24 22 20 计算第 n个Fibonacci数 其实可以在线性时间内 (以加法次数计量)完成。 但如果采用递归，递归 调用的次数是 2 Fn+1-1

问题2 相比较快速排序的分治法递 归，为什么上面的例子采用 递归代价高昂？ QUICKSORT(A,p,r) 1 if p<r 2 g PARTITION(A,p,r) 3 QUICKSORT(A,p,q-1) 4 QUICKSORT(A,g+1,r)

问题3 我们有什么办法来应对这种 情沉？ “用循环解决斐波拉契数列 的方案给我们什台启发？

Rod Cutting Problem The rod-n problem is the following.Given a rod of length n inches and a table of prices p fori1,2...determine the maximum revenue obtain- able by cttng upthe od and selling the pices. 一个样本输 入及其解： length i12345678910 price pi 1 5 8910 171720 2430 r=1 from solution 1 =1 (no cuts), r6=17 from solution 6=6 (no cuts), r2 =5 from solution 2 =2 (no cuts), 7=18 from solution 7 =1+6 or 7=2+2+3, r3 =8 from solution 3=3 (no cuts), rs 22 from solution 8=2+6, ra 10 from solution 4=2+2, r9 25 from solution 9=3+6. rs 13 from solution 5=2+3, r1o =30 from solution 10=10 (no cuts)

Rod Cutting Problem 一个样本输 入及其解： r 7:

问题4： 为什么可能的割法数量 是2n-1？

问题5： 解决问题从那里开始？ T: 我们总是要切第一刀的，但是 第一刀割在何2

我们总是要切第一刀的，但是 第一刀割在何？ r 7:

递归的解法：扫描所有可能的割法 In max (Pn:rI In-1,r2 Fn-2,...,In-1+1) Tn=max(p十Tm-i) 1<i<n 问题6： CUT-ROD(p,n) 左边的两个式子 1fn==0 2 return 0 有什么区别？ 3 9=-00 4 for i Iton 5 g max(g,p[i]+CUT-ROD(p,n-i)) 6 return 4

递归的解法：扫描所有可能的割法

最优子结构： In max (Pn:r1 In-1,r2+In-2,...,In-1+r1) 问题7 你能借助以上的式子解释一下 什么是最优子结构Optimal Substructure）？

最优子结构：