j+1
1,2,…,j
going up
可整理ppt
18
问题解答
▪ 根据递推公式可以生成两个数组up和 down数组，如下：
N=1 N=2 N=3 N=4
N=1 N=2 N=3 N=4
i=1 1
1
1i=1 0 2 0
0
i=2 0
0
1i=2 0 2 1
1
i=3 0
0
0i=3 0 2 0
1
i=4 0
0
0i=4 0 0 0
▪ 例：Fibonacci数
• F(0)=0; F(1)=1; F(n)=F(n-1)+F(n-2); • 递归: F(n-1)和F(n-2)分别求到底一次 • 动态规划：用数组将前n-1个数存起来，每次只
用一个加法 F[n] = F[n-1]+F[n-2] 即可。
可整理ppt
3
问题
A decorative fence 1037
可整理ppt
8
问题描述
样例输入： 2 21 33 样例输出： 12 231
可整理ppt
9
样例解释
2 1
2 1
3 2
1
3 2
1
3 2
1
可整理ppt
3 2
1
10
问题解答
▪ 问题分析 ▪ 对于长度为N的漂亮篱笆，其序列为：
• 以高度为1的木条开始的上升序列 • 以高度为2的木条开始的下降序列 • 以高度为2的木条开始的上升序列 • 以高度为3的木条开始的下降序列 • 以高度为3的木条开始的上升序列 • ……
• ……
可整理ppt
20
问题解答
这样就可以根据给出的序号C,判断它落 在哪一个序号区间，从而得知它的第 一根木条的高度，去除第一根木条， 余下的问题就是一个N-1难度的问题， 可以使用同样的方法求解，直到最后 一根木条的高度被确定，整个问题就 解决了。
可整理ppt
21
问题解答
这里需要注意的是，去掉第一根木条后， 余下的木条中比第一根木条高的木条 的高度要减一，才是完全的N-1难度问 题。
0
up
可整理ppt
down
19
问题解答
▪ 对于长度为N的漂亮篱笆，可以查表得到序 列：
• 以高度为1的木条开始的上升序列的个数n1 • 以高度为2的木条开始的下降序列的个数n2 • 以高度为2的木条开始的上升序列的个数n3 • 以高度为3的木条开始的下降序列的个数n4 • 以高度为3的木条开始的上升序列的个数n5
可整理ppt
22
动态规划小结
▪ 递推公式 ▪ 存储结构及内容定义 ▪ 计算顺序 ▪ 从存储结构中还原问题的解可整Fra bibliotekppt23
讨论
▪ Dividing 1014
可整理ppt
24
作业
▪ Dividing 1014 ▪ A decorative fence 1037 提高
可整理ppt
25
可整理ppt
4
问题的出处
▪ 中欧信息学奥林匹克竞赛
▪ 2002年6月30日-7月6日 ▪ 第一天: fence ▪ A decorative fence ▪ 时限: 1 s ▪ 内存: 1 MB
可整理ppt
5
问题描述
漂亮的篱笆定义如下：
▪ 篱笆由宽度相同，高度互不相同的木条组成
▪ 组成篱笆的木条高低相间，错落有致
出上升序列的个数，如下图：
可整理ppt
15
公式解释
N-i+1 N-i+1 i
i
i
i
i
i
i
x5
x1
x3
i
x2
x4
x6 x7
N+1
可整理ppt
16
公式解释
▪ 公式（3）：在以j+1开始的下降序列中， 第2个木条的可能取值是1,…,j;以它开始 的序列是上升序列，如下图：
可整理ppt
17
公式解释
going down
▪ 篱笆的长度定义为组成篱笆的木条数目N，其中木 条的高度取值（不按排列顺序）分别为1，2，…， N。
▪ 把篱笆按其木条高度顺序记为：a1a2…aN，则可以 对篱笆进行字典排序，例如：
可整理ppt
6
问题描述
长度为 4 的漂亮篱笆排序为：
1
2
3
4
5
6
7
8
9 10
可整理ppt
7
问题描述
给定篱笆长度N和在该长度下的序号C，要求 给出第C中漂亮篱笆的形状。
表示长度为N的漂亮篱笆中以高度为i的
木条开始，呈下降趋势的篱笆的个数；
•令
T up N ,i
表示长度为N的漂亮篱笆中以高度为i的
木条开始，呈上升趋势的篱笆的个数；
• 则有公式：
可整理ppt
13
问题解答
T T up
down
N,i
N,N1i
可整理ppt
（1） （2） （3）
14
公式解释
▪ 公式（1）：以1开始的下降序列为0个 ▪ 公式（2）：可以由下降序列的个数推
问题求解与程序设计 第六讲 动态规划
李文新 2004.2 – 2004.6
可整理ppt
1
内容提要
▪ 3.27-4.3一周不上课做出题作业 ▪ 动态规划 ▪ A decorative fence - 1037 ▪ 动态规划小结 ▪ 讨论 – 1014
可整理ppt
2
动态规划
▪ 与递归程序相类，将对问题求解分解为对子 问题求解；不同之处在于把子问题的解存起 来，用空间换时间。
可整理ppt
11
问题解答
▪ 问题分析
• 如果能够确定上述每一种序列的个数，就可以确 定数字C落在哪个区间，从而确定其第一个木条 的高度；则此时问题简化成N-1规模的问题，依 照同样的方法可以确定第2个木条的高度，以此 类推，可以确定所有木条的高度。
可整理ppt
12
问题解答
▪ 递推公式
•
T 令
down N ,i