(
课件网) 数据结构与算法效率 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≤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 ... ... 
