首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

4.算法设计与分析__动态规划

一、动态规划的基本思想 动态规划算法通常用于求解具有某种最优性质的问题。 在这类问题中,可能会有许多可行解。 每一个解都对应于一个值,我们希望找到具有最优值的解。 基本思想是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。 如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。 我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。 这就是动态规划法的基本思路。 具体的动态规划算法多种多样,但它们具有相同的填表格式。 二、设计动态规划法的步骤 找出最优解的性质,并刻画其结构特征; 递归地定义最优值(写出动态规划方程); 以自底向上的方式计算出最优值; 根据计算最优值时得到的信息,构造一个最优解。 步骤1~3是动态规划算法的基本步骤。 在只需要求出最优值的情形,步骤4可以省略; 若需要求出问题的一个最优解,则必须执行步骤4。 三、动态规划问题的特征 动态规划算法的有效性依赖于问题本身所具有的两个重要性质: 最优子结构: 当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。 重叠子问题: 在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只解一次,而后将其解保存在一个表格中,在以后尽可能多地利用这些子问题的解。

03
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    最长上升子序列 LIS算法实现[通俗易懂]

    有两种算法复杂度为O(n*logn)和O(n^2)。在上述算法中,若使用朴素的顺序查找在D1..Dlen查找,由于共有O(n)个元素需要计算,每次计算时的复杂度是O(n),则整个算法的时间复杂度为O(n^2),与原来算法相比没有任何进步。但是由于D的特点(2),在D中查找时,可以使用二分查找高效地完成,则整个算法时间复杂度下降为O(nlogn),有了非常显著的提高。需要注意的是,D在算法结束后记录的并不是一个符合题意的最长上升子序列!算法还可以扩展到整个最长子序列系列问题。  有两种算法复杂度为O(n*logn)和O(n^2) O(n^2)算法分析如下   (a[1]…a[n] 存的都是输入的数)   1、对于a[n]来说,由于它是最后一个数,所以当从a[n]开始查找时,只存在长度为1的不下降子序列;   2、若从a[n-1]开始查找,则存在下面的两种可能性:   (1)若a[n-1] < a[n] 则存在长度为2的不下降子序列 a[n-1],a[n].   (2)若a[n-1] > a[n] 则存在长度为1的不下降子序列 a[n-1]或者a[n]。   3、一般若从a[t]开始,此时最长不下降子序列应该是按下列方法求出的:   在a[t+1],a[t+2],…a[n]中,找出一个比a[t]大的且最长的不下降子序列,作为它的后继。   4、为算法上的需要,定义一个数组:   d:array [1..n,1..3] of integer;   d[t,1]表示a[t]   d[t,2]表示从i位置到达n的最长不下降子序列的长度   d[t,3]表示从i位置开始最长不下降子序列的下一个位置 最长不下降子序列的O(n*logn)算法   先回顾经典的O(n^2)的动态规划算法,设A[t]表示序列中的第t个数,F[t]表示从1到t这一段中以t结尾的最长上升子序列的长度,初始时设F[t] = 0(t = 1, 2, …, len(A))。则有动态规划方程:F[t] = max{1, F[j] + 1} (j = 1, 2, …, t – 1, 且A[j] < A[t])。   现在,我们仔细考虑计算F[t]时的情况。假设有两个元素A[x]和A[y],满足   (1)x < y < t (2)A[x] < A[y] < A[t] (3)F[x] = F[y]   此时,选择F[x]和选择F[y]都可以得到同样的F[t]值,那么,在最长上升子序列的这个位置中,应该选择A[x]还是应该选择A[y]呢?   很明显,选择A[x]比选择A[y]要好。因为由于条件(2),在A[x+1] … A[t-1]这一段中,如果存在A[z],A[x] < A[z] < a[y],则与选择A[y]相比,将会得到更长的上升子序列。   再根据条件(3),我们会得到一个启示:根据F[]的值进行分类。对于F[]的每一个取值k,我们只需要保留满足F[t] = k的所有A[t]中的最小值。设D[k]记录这个值,即D[k] = min{A[t]} (F[t] = k)。   注意到D[]的两个特点:   (1) D[k]的值是在整个计算过程中是单调不上升的。   (2) D[]的值是有序的,即D[1] < D[2] < D[3] < … < D[n]。   利用D[],我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断A[t]与D[len]。若A[t] > D[len],则将A[t]接在D[len]后将得到一个更长的上升子序列,len = len + 1, D[len] = A[t];否则,在D[1]..D[len]中,找到最大的j,满足D[j] < A[t]。令k = j + 1,则有D[j] < A[t] <= D[k],将A[t]接在D[j]后将得到一个更长的上升子序列,同时更新D[k] = A[t]。最后,len即为所要求的最长上升子序列的长度。   在上述算法中,若使用朴素的顺序查找在D[1]..D[len]查找,由于共有O(n)个元素需要计算,每次计算时的复杂度是O(n),则整个算法的时间复杂度为O(n^2),与原来的算法相比没有任何进步。但是由于D[]的特点(2),我们在D[]中查找时,可以使用二分查找高效地完成,则整个算法的时间复杂度下降为O(nlogn),有了非常显著的提高。需要注意的是,D[]在算法结束后记录的并不是一个符合题意的最长上升子序列!   这个算法还可以扩展到整个最长子序列系列问题,整个算法的难点在于二分查找的设计,需要非常小心注意。

    02

    动态规划(1)

    使用动态规划求解问题,最重要的就是确定动态规划三要素: (1)问题的阶段 (2)每个阶段的状态 (3)从前一个阶段转化到后一个阶段之间的递推关系。 递推关系必须是从次小的问题开始到较大的问题之间的转化,从这个角度来说,动态规划往往可以用递归程序来实现,不过因为递推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题来说,有递归不可比拟的优势,这也是动态规划算法的核心之处。 确定了动态规划的这三要素,整个求解过程就可以用一个最优决策表来描述,最优决策表是一个二维表,其中行表示决策的阶段,列表示问题状态,表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,从1行1列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

    04
    领券