动态规划.ppt

动态规划华中科技大学卢萍【例题】数字三角形设有一个三角形的数塔,顶点为根结点,每个结点有一个整数值。从顶点出发,可以向左走或向右走,如图所示: 若要求从根结点开始, 请找出一条路径,使 路径之和最大,只要输出路径的和。【问题分析】 ①贪心法往往得不到最优解: 贪心法问题所在:眼光短浅。 根据贪心法,则13-11-21和45,而实质上13-8-40和61。②若用穷举法:从根结点开始,将所有可能的路径求和,找出最大值,但算法时间复杂性使问题解成为不可能。当 N=1 P=1N=2 P=2N=3 P=4……N=K P=2K-1。当N=50,P=249=500万亿条路径。数据结构 inta[n][n];1311812726614158127132411确定状态:当前的位置(i,j)指标函数:d(i,j)----从状态(i,j)出发能得到的最大和(包括状态(i,j)本身的值)1311812726614158127132411从(i,j)出发有两种决策:(1)左下走到(i+1,j)---求d(i+1,j)(2)右下走到(i+1,j+1)---求d(i+1,j+1)取较大者状态转移方程:描述了由K阶段到K+1阶段状态的演变规律,是关于两个相邻阶段状态的方程。d(i,j)=a[i][j]+max{d[i+1,j],d[i+1,j+1]}边界:d(n,j)=a[n][j]编程计算状态转移方程1)递推2)记忆化搜索(一般在状态的拓朴顺序不很明确时使用)1)递推计算inti,j;for(j=1;j<=n;j++)d[n][j]=a[n][j];for(i=n-1;i>=1;i--)for(j=1;j<=i;j++)d[i][j]=a[i][j]+(d[i+1][j]>d[i+1][j+1]?d[i+1][j]:d[i+1][j+1])原问题的解是:d[1][1]13118127266141581271324112)记忆化搜索(一般在状态的拓朴顺序不很明确时使用,编写递归函数,需要记录每个状态是否计算过。)intdp(inti,intj){if(d[i][j]>=0)returnd[i][j];/*已被计算过*/if(i==n)return(d[i][j]=a[i][j]);if(dp(i+1,j)>dp(i+1,j+1)) return(d[i][j]=(a[i][j]+dp(i+1,j)));elsereturn(d[i][j]=(a[i][j]+dp(i+1,j+1)));}【例题】求一组数列的最长的不下降序列。 问题描述:设有一个正整数序列b1,b2,b3,……,bn,若下标为i1<i2<i3,……<ik且有bi1≤bi2≤……bik则称存在一个长度为k的不下降序列。可能有多个不下降序列,输出最长序列的长度。样例输入:13 7 9 16 38 24 37 18样例输出:5(79162437)