最优秀的投资者可以购买最多4次股票，可行方案中的一种是：
日期 2 5 6 10
价格 69 68 64 62
输入
第1行: N (1 <= N <= 5000)，股票发行天数
第2行: N个数，是每天的股票价格。
输出
输出文件仅一行包含两个数:最大购买次数和拥有最大购买次数的方案数(<=231)
当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候）,这2种方
步骤2
最优子结构性质：
设序列Xm={x1,x2,…,xm}和Yn={y1,y2,…,yn}的一个最长公共子 序列为Zk={z1,z2,…,zk}，则
1.若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序 列。
2.若xm≠yn，且zk≠xm，则Zk是Xm-1和Yn的最长公共子序列。 3.若xm≠yn，且zk≠ yn ，则Zk是Xm和Yn-1的最长公共子序列。
• 重叠子问题：在用递归算法自顶向下解问 题时，每次产生的子问题并不总是新问题 ，有些问题被反复计算多次。对每个子问 题只解一次，然后将其解保存起来，以后 再遇到同样的问题时就可以直接引用，不 必重新求解。
2020/3/5
6
动态规划 解决问题的基本特征
1. 动态规划一般解决最值（最优，最 大，最小，最长……）问题；
2020/3/5
15
拓展2：低价购买
“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟
大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买
一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标
是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内
• 以自底向上的方法来填写这表格; 首先填写最小子问题 的解.
– 这就保证了当我们解决一个特殊的子问题时, 可以 利用比它更小的所有可利用的 子问题的解.
由于历史原因, 我们称这种方法为： 动态规划.
在上世纪40年代末 (计算机普及很少时), 这些规划设计是与”列表“方法相关的.
2020/3/5
4
动态规划算法
2020/3/5
11
2020/3/5
12
程序的实现
BuyTicks(T, R)
1 n ← length[T]
2 f[0] ← 0
3 f[1] ← T[1]
4 for i ← 2 to n do
5
f[i] ← f[i-2]+R[i-1]
6
if f[i] > f[i-1]+T[i] then
7
f[i] ← f[i-1]+T[i]
2020/3/5
1
2020/3/5
2
递归 vs 动态规划
递归版本:
Hale Waihona Puke F(n)1 if n=0 or n=1 then
2
return 1
3 else
4
return F(n-1) + F(n-2)
太慢!
动态规划:
F(n)
1 A[0] = A[1] ← 1
2 for i ← 2 to n do
3
A[i] ← A[i-1] + A[i-2]
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）， 计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导 弹拦截系统。
样例： INPUT 389 207 155 300 299 170 158 65
OUTPUT 6（最多能拦截的导弹数） 2（要拦截所有导弹最少要配备的系统数）
2020/3/5
22
使用这两种操作，由一个操作数序列就可以得到一系列的输出 序列，下图所示为由1 2 3生成序列2 3 1的过程。（原始状态如 上图所示）
23
3
2
3
1 2
2 1
23
231
1
2020/3/5
23
你的程序将对给定的n，计算并输出由操作数序列1，2，…，n经过操 作可能得到的输出序列的总数。 【输入格式】 输入文件只含一个整数n（1≤n≤18） 【输出格式】 输出文件只有一行，即可能输出序列的总数目 【输入样例】 3 【输出样例】 5
• (B, C, B, A)和(B, D, A, B)都是X和Y 的最长公共子序列(长度 为4)
• 但是,(B, C, A)就不是X和Y的最长公共子序列
2020/3/5
26
穷举法
• 对于每一个Xm的子序列,验证它是否是Yn的子序列. • Xm有2m个子序列 • 每个子序列需要o(n)的时间来验证它是否是Yn的子序列.
8 return f
2020/3/5
13
例题四：求最长不降子序列
1．问题描述 设有一个正整数的序列：b1,b2,…，bn，对于下标i1<i2<…＜im，若有
bi1≤bi2≤…≤bim 则称存在一个长度为m的不下降序列。 例如，下列数列
13 7 9 16 38 24 37 18 44 19 21 22 63 15 对于下标i1=1，i2=4，i3=5，i4=9，i5=13，满足13＜16＜38＜44＜63,则存 在长度为5的不下降序列。 但是，我们看到还存在其他的不下降序列: i1=2，i2=3，i3=4，i4=8，i5＝10， i6=11，i7=12，i8=13，满足：7＜9＜16＜18＜19＜21＜22＜63，则存在长度 为8的不下降序列。 问题为：当b1,b2,…，bn给出之后，求出最长的不下降序列。
F (0,Y)=1 F (X,0)=1
步骤3：以自底向上的方法来计算最优解
2020/3/5
19
例题六：数字三角形问题
1．问题描述 设有一个三角形的数塔，顶点结点称为根结点，每个结点有一个整数数值。
从顶点出发，可以向左走，也可以向右走。如图10一1所示。
问题：当三角形数塔给出之后，找出一条从第一层到达底层的路径，使路径的 值最大。若这样的路径存在多条，任意给出一条即可。
2020/3/5
20
步骤1
二维数组 D(X,y)描述问题，D(X,y)表示从顶层到达第 X层第y个位置的最小路径得分。
阶段分析：D(1,1)=13 到第x层的第y个位置有两种可能，要
么走右分支 得到，要么走左分支得到。
步骤2：状态转移方程
•
D(X,y)＝min{D(X-1,y)，D(X-1,y-1}+a(X,y)
X的子序列: – 所有X的子集(集合中元素按原来在X中的顺序排列)
(A, B, D), (B, C, D, B), 等等.
2020/3/5
25
例子
X = (A, B, C, B, D, A, B) X = (A, B, C, B, D, A, B)
Y = (B, D, C, A, B, A)
Y = (B, D, C, A, B, A)
你的任务是，已知所有N位同学的身高，计算最少需要 几位同学出列，可以使得剩下的同学排成合唱队形。
输入的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n 个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高( 厘米)。
输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
2020/3/5
24
例题七：最长公共子序列
• 一个给定序列的子序列是在该序列中删去若干元素后得到的 序列。
• 给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子 序列时，称Z是序列X和Y的公共子序列。
• 最长公共子序列:公共子序列中长度最长的子序列。 • 最长公共子序列问题
给一定个两最个长序公列共X子=序{x列1,x。2,…,xm}和Y={y1,y2,…, yn}，找出X和Y的 • 例如: X = (A, B, C, B, D, A, B)
样例输入
样例输出：
8
4
18206201/38/56 150 200 160 130 197 220
17
2020/3/5
18
分析：阶段：棋盘上的每个可走的点； 每个阶段的求解；
步骤1：用F（X,Y）表示到棋盘上每个阶段(X,Y)的路径 条数；
步骤2：状态转移方程：
F（X,Y）= F (X-1,Y)+ F(X, Y-1) 其中，F（0,0 )=1
2. 动态规划解决的问题一般是离散 的，可以分解（划分阶段）的；
3. 动态规划解决的问题必须包含最 优子结构，即可以由（n－1）的最 优推导出n的最优
2020/3/5
7
解决问题的基本步骤
• 动态规划算法的4个步骤： 1. 刻画最优解的结构特性. （一维，二维 ，三维数组） 2. 递归的定义最优解. （状态转移方程） 3. 以自底向上的方法来计算最优解. 4. 从计算得到的解来构造一个最优解.
2020/3/5
8
2020/3/5
9
2020/3/5
10
例题三：排队买票问 题
• 一场演唱会即将举行。现有n个歌迷排队买票， 一个人买一张，而售票处规定，一个人每次最多 只能买两张票。假设第i位歌迷买一张票需要时间 Ti（1≤i≤n），队伍中相邻的两位歌迷（第j个人和 第j+1个人）也可以由其中一个人买两张票，而另 一位就可以不用排队了，则这两位歌迷买两张票 的时间变为Rj，假如Rj<Tj+Tj+1，这样做就可以缩 短后面歌迷等待的时间，加快整个售票的进程。 现给出n, Tj和Rj，求使每个人都买到票的最短时间 和方法。
步骤1：用F（i）表示第i项到最后一项最长不下降序列的长度的值；