资源简介

(共16张PPT)
数据结构与算法效率
1 斐波那契数列
为什么用动态规划算法？
3 最长公共子序列
动态规划算法如何用？
5.1数据结构与算法效率
2 最长递增子序列
什么是动态规划算法？
1
第1项
1
第2项
2
第3项
3
第4项
？
第5项

第100项
…
…
为什么n的值越大输出越慢？
？
第40项
…
…
（1）问题呈现
1.斐波那契数列
第1项
第2项
2
第3项
3
第4项
？
第5项

第100项
…
…
为什么n的值越大输出越慢？
？
第40项
…
…
F(5)
F(4)
F(3)
F(2)
F(1)
F(3)
F(2)
F(2)
F(1)
F(3)
F(3)
程序存在重复计算！
O(2n)
F(2)
F(2)
F(2)
（2）问题分析
1.斐波那契数列
第1项
第2项
2
第3项
3
第4项
？
第5项

第100项
…
…
如何提高算法的效率？
？
第40项
…
…
将函数的值记录下来。
（3）问题解决
1.斐波那契数列
第1项
第2项
2
第3项
3
第4项
？
第5项

第100项
…
…
？
第40项
…
…
S[i]记录函数F(i)的值，减少重复计算。
★递推 + 记录(空间换时间)
（4）程序实现
1.斐波那契数列
例1 求最长递增子序列的长度。如：nums = [1,7,5,6,8,2]
最长递增子序列为[1,5,6,8]，其长度为4。
（1）问题分析
2.最长递增子序列
设L(i)表示以nums[i]结尾的最长递增子序列的长度
L(5) [1,2],[2] [1,2] 2
L(4) [1,8],[1,7,8],[1,5,8],[1,5,6,8],[8] [1,5,6,8] 4
L(3) [1,6],[1,5,6],[6] [1,5,6] 3
L(2) [1,5],[5] [1,5] 2
L(1) [1,7],[7] [1,7] 2
L(0) [1] [1] 1
③
求出
最大值
递增
最长
长度
L(4) [1,8],[1,7,8],[1,5,8],[1,5,6,8],[8] [1,5,6,8] 4
最优解
最优子结构
①列出
②找出
L(5)
L(3)
L(2)
L(1)
L(0)
L(4)
×
×
×
×
L(4)
L(3)
L(2)
L(1)
L(0)
L(3)
L(2)
L(1)
L(0)
×
L(2)
L(1)
L(0)
L(2)
×
L(0)
L(1)
L(2)
L(1)
L(0)
L(2)
×
L(5) = max({L(0)}) +1
L(4) = max({L(0),L(1), L(2), L(3))+1
L(3) = max({L(0), L(2)})+1
L(2) = max({L(0)})+1
L(1) = max(L(0))+1
L(0) = 1
max(L(j))+1 , 0≤j1, 其他情况
求最大值
L(i) =
（2）抽象建模
例1 求最长递增子序列的长度。如：nums = [1,7,5,6,8,2]
最长递增子序列为[1,5,6,8]，其长度为4。
L(2)
L(2)
自顶向下分析，计算L(i)需要用到L(j)的值，
自底向上实现，先计算较小的L(j)再计算较大的L(i)。
2.最长递增子序列
动态规划算法将一个问题划分成较小规模的子问题，先解决小规模的子问题，使用数组或列表存储动态产生的结果，需要这个结果时无须重新计算就能直接使用。
特点:(1)重复子问题
(2)最优子结构
动态规划算法应用：组合优化问题。
（3）设计算法
2.最长递增子序列
例1 求最长递增子序列的长度。
如：nums = [1,7,5,6,8,2]
最长递增子序列为[1,5,6,8]，其长度为4。
（3）设计算法
d[i]记录函数L(i)的值，减少重复计算。
★递推 + 记录(空间换时间)
2.最长递增子序列
1
7
5
6
8
2
nums[i]
d[i]
i
1
0 1 2 3 4 5
1
1
i
7
2
5
6
8
2
2
3
4
2
7
5
6
8
2
i
i
i
i

（4）程序实现
2.最长递增子序列
3.最长公共子序列
（1）问题分析
例2 求最长公共子序列的长度。(教材P49）
如：S1为 TAGCCTAGCG
S2为 TACAGA最长的公共子序列是TACAG，长度为5。
选取部分进行分析,X序列:CCTA,Y序列:TACA
（2）抽象建模
选取部分进行分析,X序列:CCTA,Y序列:TACA
设LCS(Xi,Yj)表示序列X的前i个元素和序列Y的前j个元素的最长公共子序列长度
0 , i=0或j=0
LCS(Xi-1,Yj-1)+1, i,j>0 且 Xi=Yj
max(LCS(Xi-1,Yj), LCS(Xi,Yj-1)) i,j>0 且 Xi≠Yj
LCS(Xi,Yj) =
计算LCS(Xi,Yj)需要用到LCS(Xi-1,Yj-1)、 LCS(Xi-1,Yj)、 LCS(Xi,Yj-1)的值
先计算较小的子问题的最优解，再计算较大的子问题的最优解。
LCS(X3,Y3)
LCS(X2,Y2)
LCS(X1,Y2)
LCS(X2,Y1)
LCS(X2,Y0)
LCS(X1,Y1)
LCS(X0,Y1)
LCS(X0,Y1)
LCS(X1,Y0)
LCS(X0,Y1)
LCS(X0,Y1)
3.最长公共子序列
[练一练]请暂停视频，写出函数的形式化表达。
T A C A
0 0 0 0 0
C 0
C 0
T 0
A 0
（3）设计算法
LCS[i][j]记录LCS(Xi,Yj)值，减少重复计算。
if X[i] == Y[j]: LCS[i][j] = LCS[i- 1][j - 1] + 1
if X[i] != Y[j]: LCS[i][j] = max(LCS[i - 1][j],LCS[i][j-1])
↑0
0
1
1
最长公共子序列为TA或CA，
长度为2。
↑0
0
1
1
1
1
1
1
↑1
2
2
2
3.最长公共子序列
0 1 2 3 4
0 1 2 3 4
（4）程序实现
3.最长公共子序列
动态规划算法
小问题推大问题
大问题分小问题
算法思想
重复子问题
最优
子结构
适用范围
自顶向下分析
自底向上实现
求解步骤
斐波那契数列
最长递增子序列
最长公共子序列
应用实例

展开更多......

收起↑