算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第5章）

《算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第5章）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章动态规划法动态规划法的基本思想序列和数组问题的动态规划算法图中的动态规划算法动态规划法的基本思想重叠子问题最优性原则5.1动态规划法的基本思想重叠子问题Fib(5)斐波那契数列的递归算法Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(1)Fib(2)Fib(1)5.1动态规划法的基本思想重叠子问题斐波那契数列的动态规划算法Fib(3)Fib(2)Fib(1)Fib(4)Fib(5)5.1动态规划法的基本思想重叠子问题最优性原则一个问题的最优解必然包含其子问题的最优解首尔北京上海西安成都重庆九寨沟8008209801100

2、1200125090011905005504805.1动态规划法的基本思想重叠子问题最优性原则min(首尔,北京)=800min(首尔,上海)=820首尔北京上海西安成都重庆九寨沟8008209801100120012509001190500550480一个问题的最优解必然包含其子问题的最优解5.1动态规划法的基本思想重叠子问题最优性原则min(首尔,北京)=800min(首尔,上海)=820min(首尔,西安)=1780min(首尔,重庆)=1720min(首尔,成都)=2000首尔北京上海西安成都重庆九寨沟800820980110012001

3、2509001190500550480一个问题的最优解必然包含其子问题的最优解5.1动态规划法的基本思想重叠子问题最优性原则min(首尔,北京)=800min(首尔,上海)=820min(首尔,西安)=1780min(首尔,重庆)=1720min(首尔,成都)=2000min(首尔,九寨沟)=2270首尔北京上海西安成都重庆九寨沟8008209801100120012509001190500550480一个问题的最优解必然包含其子问题的最优解5.2计算二项式系数5.2计算二项式系数重叠子问题C(n,k)C(n−1,k)C(n−1,k−1)C(n−

4、2,k)C(n−2,k−1)C(n−2,k−1)C(n−2,k−2)C(n−3,k)C(n−3,k−1)C(n−3,k−1)C(n−3,k−2)C(n−3,k−1)C(n−3,k−2)C(n−3,k−2)C(n−3,k−3)……5.2计算二项式系数重叠子问题……序列和数组问题的动态规划算法最长连续上升子序列问题最大子段和问题最长公共子序列问题5.3最长连续上升子序列问题输入:一组可比较元素组成的序列输出:元素连续上升的最长一段子序列18151210201681424185.3最长连续上升子序列问题1815121020168142418lis(A[

5、0..n−1])=(Max(i,j):0≤i≤j

6、A[i..j]

7、)O(n2)5.3最长连续上升子序列问题1815121020168142418lis'(A[0..n−1])=(Maxi:0≤i

8、A[i..n−1]

9、)1212312121lis(A[0..n−1])=(Max(i,j):0≤i≤j

10、A[i..j]

11、)O(n2)O(n)5.3最长连续上升子序列问题[动态规划算法]AlgorithmLongestIn

12、cSubseq(A:T[])beginletn=

13、A

14、,lis=lis'=1;fori=0ton-2doif(A[i]≥A[i+1])thenlis'1;elselis'lis'+1;if(lis'>lis)thenlislis';returnlis;end5.4最大子段和问题输入:数组A[0..n−1]输出:元素之和最大的一段子数组rs(A[0..n−1])≡(Maxi:0≤i

15、和问题[动态规划算法]AlgorithmMaxSum(A:int[])beginletn=

16、A

17、,a=b=0;fori=0ton-1doif(b≤0)thenbA[i];elsebb+A[i];if(b>a)thenab;returna;end5.4最大子段和问题扩展:二维数组（矩阵）的最大子段（子矩阵）和5.5最长公共子序列问题输入:序列Am和Bn输出:两个序列的最长公共子序列5.5最长公共子序列问题5.5最长公共子序列问题AlgorithmLongestComSubseq(A,B:T[])beginletm=

18、A

19、,n=

20、B

21、,X

22、=newT[m][];fori=0tomdo//初始化第0行if(A[i]=B[0])thenX[i][B[0]];elseX[i]