精华内容
下载资源
问答
  • 动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。 什么是动态规划 动态规划(Dynamic Programming)对于子问题重叠的情况特别有效,因为它将子问题...

    动态规划(Dynamic programming)

    是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。

     

    什么是动态规划

        动态规划(Dynamic Programming)对于子问题重叠的情况特别有效,因为它将子问题的解保存在表格中,当需要某个子问题的解时,直接取值即可,从而避免重复计算!

        动态规划是一种灵活的方法,不存在一种万能的动态规划算法可以解决各类最优化问题(每种算法都有它的缺陷)。所以除了要对基本概念和方法正确理解外,必须具体问题具体分析处理,用灵活的方法建立数学模型,用创造性的技巧去求解。

     

    基本策略

        基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

        动态规划中的子问题往往不是相互独立的(即子问题重叠)。在求解的过程中,许多子问题的解被反复地使用。为了避免重复计算,动态规划算法采用了填表来保存子问题解的方法。

     

    适用问题

    那么什么样的问题适合用动态规划的方法来解决呢?

        适合用动态规划来解决的问题,都具有下面三个特点:最优化原理、无后效性、有重叠子问题

     

    (1)最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。

    (2)无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。

    (3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势。

     

    这类问题的求解步骤通常如下:

    初始状态→│决策1│→│决策2│→…→│决策n│→结束状态

    (1)划分:按照问题的特征,把问题分为若干阶段。注意:划分后的阶段一定是有序的或者可排序的

    (2)确定状态和状态变量:将问题发展到各个阶段时所处的各种不同的客观情况表现出来。状态的选择要满足无后续性

    (3)确定决策并写出状态转移方程:状态转移就是根据上一阶段的决策和状态来导出本阶段的状态。根据相邻两个阶段状态之间的联系来确定决策方法和状态转移方程

    (4)边界条件:状态转移方程是一个递推式,因此需要找到递推终止的条件

     

    算法实现

    动态规划三要素:

    (1)问题的阶段

    (2)每个阶段的状态

    (3)相邻两个阶段之间的递推关系

    整个求解过程可以用一张最优决策表来描述,最优决策表是一张二维表(行:决策阶段,列:问题的状态)表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

    例如:f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

     

    1 事例一背包问题

    问题描述:假设我们有n种类型的物品,分别编号为1, 2...n。其中编号为i的物品价值为vi,它的重量为wi。为了简化问题,假定价值和重量都是整数值。现在,假设我们有一个背包,它能够承载的重量是Cap。现在,我们希望往包里装这些物品,使得包里装的物品价值最大化,那么我们该如何来选择装的东西呢?注意:每种物品只有一件,可以选择放或者不放。初始化数据为:n=5,w={2,2,6,5,4},v={6,3,5,4,6},Cap=10

    解法如下:

    A)描述最优解的结构

    设子问题:f[i][v]表示允许前i件物品放入容量为v的背包时可以获得的最大价值。注:这里的i从0到5,v从0到10

    为了能够得到已经计算过的,更小规模的子问题,我们可以根据当前限重来只考虑第i件物品放或者不放,那么就可以转化为涉及前i-1件物品的问题,

    即:

    情况1、如果第i件物品不能放(即这个物品的重量直接大于了当前限重v),则问题转化为“前i-1件物品放入容量为v的背包中”,即f[i-1][v];

    情况2、如果放第i件物品是可以放也可以不放,则问题转化为:

    1)、如果选择不放第i件物品,则问题转化为“前i-1件物品放入容量为v的背包中”,即变大时f[i-1][v];

    2)、如果选择放第i件物品,则问题转化为“前i-1件物品放入剩下的容量为v-w[i]的背包中”,此时能获得的最大价值就是f [i-1][v-w[i]]再加上通过放入第i件物品获得的价值v[i]。

    则情况2下,f[i][v]的值就是1),2)中最大的那个值。

    最优子结构描述如下:当子问题f[i][v]是最优时,其子问题f[i-1][v]和f[i-1][v-w[i]](中的较大者)显然同样也必须是最优的值,不然在情况1或者情况2下总会矛盾。

    B) 递归定义最优解的值

    根据上面的分析,显然子问题

    f[i][v]=f[i-1][v],这时是情况1

    f[i][v]=max{f[i-1][v], f[i-1][v-w[i]]+v[i] },这时是情况2。

    C)按自底而上的方式计算最优解的值

    import numpy as np
     
    #行李数n,不超过的重量W,重量列表w和价值列表p
    def fun(n,W,w,p):
    	a=np.array([[0]*(W+1)]*(n+1))
    	#依次计算前i个行李的最大价值,n+1在n的基础上进行
    	for i in range(1,n+1):
    		for j in range(1,W+1):
    			if w[i-1]>j:
    				a[i,j]=a[i-1,j]
    			else:
    				a[i,j]=max(a[i-1,j],p[i-1]+a[i-1,j-w[i-1]])#2种情况取最大值
    	#print(a)
    	print('max value is'+str(a[n,W]))
    	findDetail(p,n,a[n,W])
    #找到价值列表中的一个子集,使得其和等于前面求出的最大价值,即为选择方案
    def findDetail(p,n,v):
    	a=np.array([[True]*(v+1)]*(n+1))
    	for i in range(0,n+1):
    		a[i][0]=True
    	for i in range(1,v+1):
    		a[0][i]=False
    	for i in range(1,n+1):
    		for j in range(1,v+1):
    			if p[i-1]>j:
    				a[i,j]=a[i-1,j]
    			else:
    				a[i,j]=a[i-1,j] or a[i-1,j-p[i-1]]
    	if a[n,v]:
    		i=n
    		result=[]
    		while i>=0:
    			if a[i,v] and not a[i-1,v]:
    				result.append(p[i-1])
    				v-=p[i-1]
    			if v==0:
    				break
    			i-=1
    		print(result)
    	else:
    		print('error')
    weights=[1,2,5,6,7,9]
    price=[1,6,18,22,28,36]
    fun(len(weights),13,weights,price)

    2 事例二

    有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。

    分析:动态规划的实现的关键在于能不能准确合理的用动态规划表来抽象出 实际问题。在这个问题上,我们让f(n)表示走上n级台阶的方法数。

    那么当n为1时,f(n) = 1,n为2时,f(n) =2,就是说当台阶只有一级的时候,方法数是一种,台阶有两级的时候,方法数为2。那么当我们要走上n级台阶,必然是从n-1级台阶迈一步或者是从n-2级台阶迈两步,所以到达n级台阶的方法数必然是到达n-1级台阶的方法数加上到达n-2级台阶的方法数之和。即f(n) = f(n-1)+f(n-2),我们用dp[n]来表示动态规划表,dp[i],i>0,i<=n,表示到达i级台阶的方法数。

    class Solution:
        """
        @param n: an integer
        @return: an ineger f(n)
        """
    
        def up(self, n):
            # write your code here
            # if n == 0:
            #     return 0
            L = []
            L.append(1)
            L.append(2)
            for i in range(2, n):
                L.append(L[i - 1] + L[i - 2])
            return L[n - 1]

    3 事例三

    给定一个矩阵m,从左上角开始每次只能向右走或者向下走,最后达到右下角的位置,路径中所有数字累加起来就是路径和,返回所有路径的最小路径和,如果给定的m如下,那么路径1,3,1,0,6,1,0就是最小路径和,返回12.

    1 3 5 9

    8 1 3 4

    5 0 6 1

    8 8 4 0

    分析:对于这个题目,假设m是m行n列的矩阵,那么我们用dp[m][n]来抽象这个问题,dp[i][j]表示的是从原点到i,j位置的最短路径和。我们首先计算第一行和第一列,直接累加即可,那么对于其他位置,要么是从它左边的位置达到,要么是从上边的位置达到,我们取左边和上边的较小值,然后加上当前的路径值,就是达到当前点的最短路径。然后从左到右,从上到下依次计算即可。

    m[i][j] = min(m[i-1][j],m[i][j-1]) + p[i][j]

    代码不再详细写,与背包问题类似的矩阵求解。

    4 事例四

    给定两个字符串str1和str2,返回两个字符串的最长公共子序列,例如:str1="1A2C3D4B56",str2="B1D23CA45B6A","123456"和"12C4B6"都是最长公共子序列,返回哪一个都行。

    分析:本题是非常经典的动态规划问题,假设str1的长度为M,str2的长度为N,则生成M*N的二维数组dp,dp[i][j]的含义是str1[0..i]与str2[0..j]的最长公共子序列的长度。

    dp值的求法如下:

    dp[i][j]的值必然和dp[i-1][j],dp[i][j-1],dp[i-1][j-1]相关,结合下面的代码来看,我们实际上是从第1行和第1列开始计算的,而把第0行和第0列都初始化为0,这是为了后面的取最大值在代码实现上的方便,dp[i][j]取三者之间的最大值。

    # 此例中有多个相同长度的公共子串,但只能获取第一个子串
    def find_lcsubstr(s1, s2): 
    	# 下面4行不要直接写在循环中,减少计算
    	s1_len = len(s1) + 1 					#为方便后续计算,多了1行1列 
    	s2_len = len(s2) + 1
    	s3_len = len(s1)
    	s4_len = len(s2)
    	m = [[0 for j in range(s2_len)] for i in range(s1_len)] #生成0矩阵
    	maxNum = 0   							#初始最长匹配长度
    	p = 0  									#匹配的起始位置
    	for i in range(s3_len):
    		for j in range(s4_len):
    			if s1[i] == s2[j]:				  #相同则累加
    				m[i + 1][j + 1] = m[i][j] + 1 #给相同字符赋值,值为左上角值加1
    				if m[i + 1][j + 1] > maxNum:
    					maxNum = m[i + 1][j + 1]  #获取最大匹配长度
    					p = i + 1 				  #记录最大匹配长度的终止位置
    	print(m)
    	return s1[p - maxNum : p], maxNum   	  #返回最长子串及其长度
    print(find_lcsubstr(str_a, str_b))
    

    5 事例五

    把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

    解题思路:这个用动态规划感觉就很好啦

    终止条件:第N个丑数

    状态:s[i] 第i个丑数

    状态转移方程: s[i] = min(s[t1]*2 , s[t2]*3, s[t3]*5)。这个t1,t2,t3<i-1

    这3个t怎么确定呢?从i-1往后倒腾,满足s[t1-1]*2小于等于s[i-1]但s[t1]*2大于s[i-1]

    确定了之后敲代码把~~(代码还有很多可以优化的,但觉得这个可读性比较强,贴上自己的代码)
     

    class Solution:
        def GetUglyNumber_Solution(self, index):
            if index<1:
                return 0
            if index==1:
                return 1
            s = []
            s.append(1)
            t1 = 0
            t2 = 0
            t3 = 0
            for i in range(1,index):            
                for j in range(i):
                    if s[j]*2 > s[i-1]:
                        t1 = j
                        break
                for j in range(i):
                    if s[j]*3 > s[i-1]:
                        t2 = j
                        break
                for j in range(i):
                    if s[j]*5 > s[i-1]:
                        t3 = j   
                        break
                s.append(min(s[t1]*2,s[t2]*3,s[t3]*5))
                
            return s[-1]
    

    6 事例六

    找零钱问题,已经零钱面额为1、3、4,求找零n所用零钱数最少的方案

    解答过程:对于找零n的最少零钱数f(n),它和f(n-1),f(n-3),f(n-4)有关,即它等于这3者中最小的值加1.

    # 找零钱字典,key为面额,value为最少硬币数
    change_dict = {}
     
    def rec_change(M, coins):
        change_dict[0] = 0
        s = 0
     
        for money in range(1, M+1):
            num_of_coins = float('inf')
            #意思是要求50的最少找零数,在46,47,49的最少找零数中找到最小的即可
            for coin in coins:
                if money >= coin:
                    # 记录每次所用的硬币数量
                    if change_dict[money-coin]+1 < num_of_coins:
                        num_of_coins = change_dict[money-coin]+1
                        s = coin #记录每次找零的面额
     
            change_dict[money] = num_of_coins
        return change_dict[M],s
     
    # 求出具体的找零方式
    # 用path变量记录每次找零的面额
    def method(M, coins):
        print('Total denomination is %d.'%M)
        nums, path = rec_change(M, coins)#path为最少硬币数方案中的一个面额值
        print('The smallest number of coins is %d.'%nums)
        print('%s'%path, end='')
     
        while M-path > 0:
            M -= path
            nums, path = rec_change(M, coins)
            print(' -> %s'%path, end='')
        print()
     
    coins = (1, 3, 4)
    method(50, coins)

    7 事例七

    钢条切割,已经各长度的钢条和对应的收益,问长度为n的钢条怎么切割收益最大。

    要求长度为n的钢条切割最大收益,则在n-1最大收益+长度1的收益,n-2最大收益+长度2最大收益……中取最大者。那么依次求长度1~n的钢条最大收益即可。

    # 钢条长度与对应的收益
    length = (1, 2, 3, 4,5, 6, 7, 8, 9, 10)
    profit = (1, 5, 8, 9,10, 17, 17, 20, 24, 30)
     
     
    # 参数:profit: 收益列表, n: 钢条总长度
    def bottom_up_cut_rod(profit, n):
        r = [0] # 收益列表
        s = [0]*(n+1) # 切割方案列表
     
        for j in range(1, n+1):
            q = float('-inf')
            #每次循环求出长度为j的钢条切割最大收益r[j],s[j]则保存切割方案中最长的那一段长度
            for i in range(1, j+1):
                if max(q, profit[length.index(i)]+r[j-i]) == profit[length.index(i)]+r[j-i]:#元组index从1开始
                    s[j] = i#如果切割方案为1和2,那么2会覆盖1,即保存最长的一段
                q = max(q, profit[length.index(i)]+r[j-i])
     
            r.append(q)
            #r[n]保存长度为n钢条最大切割收益
        return r[n], s[n]
     
    # 切割方案
    def rod_cut_method(profit, n):
        how = []
        while n != 0:
            t,s = bottom_up_cut_rod(profit, n)
            how.append(s)
            n -= s
     
        return how
    #输出长度1~10钢条最大收益和最佳切割方案
    for i in range(1, 11):
        t1 = time.time()
        money,s = bottom_up_cut_rod(profit, i)
        how =  rod_cut_method(profit, i)
        t2 = time.time()
        print('profit of %d is %d. Cost time is %ss.'%(i, money, t2-t1))
        print('Cut rod method:%s\n'%how)

    8 事例八

    水杯摔碎问题,有n个水杯和k层楼,求最少测试几次可以确定水杯刚好在哪一层楼摔碎。

    解答过程:假设从x层楼开始扔为f(n,x),如果水杯碎了水杯数量-1需要探测的楼层为x-1层,则为f(n-1,x-1),如果没碎水杯还是n个需要探测k-x层,则为f(n,k-x)

    import numpy as np
     
    #n个水杯k层楼,最少需要几次测试确定水杯在几层楼刚好摔破
    def solvepuzzle(n, k):
        numdrops = np.array([[0]*(k+1)]*(n+1))
     
        for i in range(k+1):
            numdrops[1, i] = i#只有一个水杯,最坏情况是跟楼层数一样
     
        for i in range(2, n+1):#2到n个水杯
            for j in range(1, k+1):#楼层1到k
                minimum = float('inf')
                #每次循环得出一种(i,j)下的最少次数
                for x in range(1, j+1):
                    minimum = min(minimum, (1+max(numdrops[i, j-x], numdrops[i-1, x-1])))
                numdrops[i, j] = minimum
        print(numdrops)
        return numdrops[n,k]
     
    t = solvepuzzle(3, 10)
    print(t)

    9 事例九

    给定n个水杯和d次尝试机会,求最多能探测多少楼层。

    解答过程:f(d,n)=f(d-1,n)+f(d-1,n-1),令g(d,n)=f(d,n+1)-f(d,n)=g(d-1,n)+g(d-1,n-1),这跟二项式C(n,k)=C(n-1,k)+C(n-1,k-1)相似,故g(d,n)=C(d,n)-->f(d,n)=求和(C(d,i)) i从1到n-1,i>=d时C(d,i)=0

    
    #n个水杯d次尝试机会,最多探测多少层楼?
    #f(d,n)=求和i=1~n-1{C(d,i)} 对所有d>=1 and i<d
    def assist(d,i):#C(d,i)
    	sum=1
    	sum2=1
    	for k in range(d-i+1,d+1):
    		sum*=k
    	for j in range(1,i+1):
    		sum2*=j
     
    	sum=sum/sum2
    	return sum
     
    def f(d,n):
    	if d<1 or n<1:
    		return 0
    	elif d==1:
    		return 1
    	sum=0
    	for i in range(1,n+1):
    		if i<d:
    			sum+=assist(d,i)
    	return int(sum)
    print(f(3,3))
    #这里可以逆向求解n个水杯k层楼至少需要多少次测试
    def reverseFun(n,k):
    	d=1
    	while f(d,n)<k:
    		d+=1
    	print(d)
    	return d
    reverseFun(3,10)

     

    展开全文
  • 动态规划算法

    千次阅读 2015-08-02 09:45:57
    决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。 二、基本思想与策略 基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解...

    一、基本概念

        动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。

    二、基本思想与策略

        基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

        由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。

        与分治法最大的差别是:适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)

     


    三、适用的情况

    能采用动态规划求解的问题的一般要具有3个性质:

        (1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。

        (2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。

       (3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势

     


    四、求解的基本步骤

         动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式,一般要经历以下几个步骤。

       初始状态→│决策1│→│决策2│→…→│决策n│→结束状态

                          图1 动态规划决策过程示意图

        (1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。

        (2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。

        (3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程

        (4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。

        一般,只要解决问题的阶段状态状态转移决策确定了,就可以写出状态转移方程(包括边界条件)。

    实际应用中可以按以下几个简化的步骤进行设计:

        (1)分析最优解的性质,并刻画其结构特征。

        (2)递归的定义最优解。

        (3)以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值

        (4)根据计算最优值时得到的信息,构造问题的最优解

     


    五、算法实现的说明

        动态规划的主要难点在于理论上的设计,也就是上面4个步骤的确定,一旦设计完成,实现部分就会非常简单。

         使用动态规划求解问题,最重要的就是确定动态规划三要素

        (1)问题的阶段 (2)每个阶段的状态

        (3)从前一个阶段转化到后一个阶段之间的递推关系

         递推关系必须是从次小的问题开始到较大的问题之间的转化,从这个角度来说,动态规划往往可以用递归程序来实现,不过因为递推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题来说,有递归不可比拟的优势,这也是动态规划算法的核心之处

        确定了动态规划的这三要素,整个求解过程就可以用一个最优决策表来描述最优决策表是一个二维表,其中行表示决策的阶段,列表示问题状态,表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,从1行1列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

              f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}


    六、动态规划算法基本框架

    复制代码
    代码
     
    1 for(j=1; j<=m; j=j+1) // 第一个阶段 2   xn[j] = 初始值; 3 4  for(i=n-1; i>=1; i=i-1)// 其他n-1个阶段 5   for(j=1; j>=f(i); j=j+1)//f(i)与i有关的表达式 6 xi[j]=j=max(或min){g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])}; 8 9 t = g(x1[j1:j2]); // 由子问题的最优解求解整个问题的最优解的方案 10 11 print(x1[j1]); 12 13 for(i=2; i<=n-1; i=i+1 15 { 17 t = t-xi-1[ji]; 18 19 for(j=1; j>=f(i); j=j+1) 21 if(t=xi[ji]) 23 break; 25 } 七、动态规划经典题目

    1.最大连续子序列之和

    解法1—O(N^2)解法

    因为最大连续子序列和只可能从数组0到n-1中某个位置开始,我们可以遍历0到n-1个位置,计算由这个位置开始的所有连续子序列和中的最大值。最终求出最大值即可。

    更详细的讲,就是计算从位置0开始的最大连续子序列和,从位置1开始的最大连续子序列和。。。直到从位置n-1开始的最大连续子序列和,最后求出所有这些连续子序列和中的最大值就是答案。

    解法2—O(NlgN)解法

    该问题还可以通过分治法来求解,最大连续子序列和要么出现在数组左半部分,要么出现在数组右半部分,要么横跨左右两半部分。因此求出这三种情况下的最大值就可以得到最大连续子序列和。

    解法3—O(N)解法

    还有一种更好的解法,只需要O(N)的时间。因为最大 连续子序列和只可能是以位置0~n-1中某个位置结尾。当遍历到第i个元素时,判断在它前面的连续子序列和是否大于0,如果大于0,则以位置i结尾的最大连续子序列和为元素i和前门的连续子序列和相加;否则,则以位置i结尾的最大连续子序列和为元素i。

    package 动态规划;
    public class 最大连续子序列之和 {
    	
    	public static void main(String args[]) {
    		// TODO Auto-generated method stub
    		int arr[] = {3,-4,1,5,2};
    		System.out.println("解法1—O(N^2)解法 : " + maxsequence1(arr, 5) );
    		System.out.println("解法2—O(NlgN)解法 : " + maxsequence2(arr, 1,4) );
    		System.out.println("解法3—O(N)解法 : " + maxsequence3(arr, 5) );
    			
    		
    	}
    	
    	//解法1—O(N^2)解法 :
    	public static int maxsequence1(int arr[], int len)  
        {  
            int max = arr[0]; //初始化最大值为第一个元素  
            for (int i=0; i max)  
                        max = sum;  
                }  
            }  
            return max;  
        }  
    	
    	//解法2—O(NlgN)解法 
       public static int maxsequence2(int a[], int l, int u)  
        {  
            if (l > u) return 0;  
            if (l == u) return a[l];  
            int m = (l + u) / 2;  
          
            /*求横跨左右的最大连续子序列左半部分*/     
            int lmax=a[m], lsum=0;  
            for (int i=m; i>=l; i--) {  
                lsum += a[i];  
                if (lsum > lmax)  
                    lmax = lsum;  
            }  
              
            /*求横跨左右的最大连续子序列右半部分*/     
            int rmax=a[m+1], rsum = 0;   
            for (int i=m+1; i<=u; i++) {   
                rsum += a[i];  
                if (rsum > rmax)   
                    rmax = rsum;   
            }  
            return max3(lmax+rmax, maxsequence2(a, l, m), maxsequence2(a, m+1, u)); //返回三者最大值  
        }  
          
        /*求三个数最大值*/  
       public static  int max3(int i, int j, int k)  
        {  
            if (i>=j && i>=k)  
                return i;  
            return max3(j, k, i);  
        }   
       
       //解法3—O(N)解法
       public static int maxsequence3(int a[], int len)  
       {  
           int maxsum, maxhere;  
           maxsum = maxhere = a[0];   //初始化最大和为a【0】  
           for (int i=1; i maxsum) {  
                   maxsum = maxhere;  //更新最大连续子序列和  
               }  
           }  
           return maxsum;  
       }  
    }
     max)  
                        max = sum;  
                }  
            }  
            return max;  
        }  
    	
    	//解法2—O(NlgN)解法 
       public static int maxsequence2(int a[], int l, int u)  
        {  
            if (l > u) return 0;  
            if (l == u) return a[l];  
            int m = (l + u) / 2;  
          
            /*求横跨左右的最大连续子序列左半部分*/     
            int lmax=a[m], lsum=0;  
            for (int i=m; i>=l; i--) {  
                lsum += a[i];  
                if (lsum > lmax)  
                    lmax = lsum;  
            }  
              
            /*求横跨左右的最大连续子序列右半部分*/     
            int rmax=a[m+1], rsum = 0;   
            for (int i=m+1; i<=u; i++) {   
                rsum += a[i];  
                if (rsum > rmax)   
                    rmax = rsum;   
            }  
            return max3(lmax+rmax, maxsequence2(a, l, m), maxsequence2(a, m+1, u)); //返回三者最大值  
        }  
          
        /*求三个数最大值*/  
       public static  int max3(int i, int j, int k)  
        {  
            if (i>=j && i>=k)  
                return i;  
            return max3(j, k, i);  
        }   
       
       //解法3—O(N)解法
       public static int maxsequence3(int a[], int len)  
       {  
           int maxsum, maxhere;  
           maxsum = maxhere = a[0];   //初始化最大和为a【0】  
           for (int i=1; i maxsum) {  
                   maxsum = maxhere;  //更新最大连续子序列和  
               }  
           }  
           return maxsum;  
       }  
    }
    

    2.数塔问题

    • /* 
    • 数塔问题: 
    • 12 15 
    • 10 6 8 
    • 2 18 9 5 
    • 19 7 10 4 16 
    • 有形如图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走, 
    • 一直走到底层,要求找出一条路径,使路径上的值最大。 
    • 这道题如果用枚举法,在数塔层数稍大的情况下(如40),则需要列举出的路径条数将是一个非常庞大的数目。 
    • 如果用贪心法又往往得不到最优解。 
    • 在用动态规划考虑数塔问题时可以自顶向下的分析,自底向上的计算。 
    • 从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值, 
    • 只要左右两道路径上的最大值求出来了才能作出决策。 
    • 同样的道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。 
    • 这样一层一层推下去,直到倒数第二层时就非常明了。 
    • 如数字2,只要选择它下面较大值的结点19前进就可以了。 
    • 所以实际求解时,可从底层开始,层层递进,最后得到最大值。 
    • 总结:此题是最为基础的动态规划题目,阶段、状态的划分一目了然。 
    •       而决策的记录,充分体现了动态规划即“记忆化搜索”的本质。 
    • */ 
      package 动态规划;
      
      public class 数塔问题 {
      
      	public static void main(String[] args) {
      		// TODO Auto-generated method stub
      		int i,j;  
      	    int data[][] = {  
      	            {9,0,0,0,0},  
      	            {12,15,0,0,0},  
      	            {10,6,8,0,0},  
      	            {2,18,9,5,0},  
      	            {19,7,10,4,16}  
      	        };  
      	        for(i = 4; i > 0; i--)  
      	            for(j = 0; j < i; j++)  
      	                data[i-1][j] += data[i][j] > data[i][j+1] ? data[i][j] : data[i][j+1];  
      	          
      	       System.out.println(data[0][0]);  
      	}
      
      }
      

      3.背包问题

      package 动态规划;
      
      public class 背包问题 {
      
      	public static void main(String[] args) {
      		// TODO Auto-generated method stub
      		int v = 10 ;    
      	    int n = 5 ;      
      	       
      	    int value[] = {0, 8 , 10 , 4 , 5 , 5};       
      	    int weight[] = {0, 6 , 4 , 2 , 4 , 3};     
      	    int i,j;      
      	    int[][] dp= new int[n+1][v+1];  
      	    for(i = 0; i < n+1; i++)  
      	        for(j = 0; j < v+1; j++)  
      	            dp[i][j] = 0;  
      	  
      	  
      	    for(i = 1; i <= n; i++){  
      	        for(j = 1; j <= v; j++){  
      	            if(j >= weight[i])  {
      	            	int max = dp[i-1][j]>(dp[i-1][j-weight[i]] + value[i]) ? dp[i-1][j] :(dp[i-1][j-weight[i]] + value[i]);
      	            	dp[i][j]=max;
      	            }
      	            else  
      	                dp[i][j] = dp[i-1][j];  
      	        }  
      	    }  
      	  
      	    System.out.println(dp[n][v]);  
      	}
      
      }
      

      更多参考:http://blog.csdn.net/zmazon/article/details/8247015


      搜索与推荐Wiki

      扫一扫 关注微信公众号!号主 专注于搜索和推荐系统,尝试使用算法去更好的服务于用户,包括但不局限于机器学习,深度学习,强化学习,自然语言理解,知识图谱,还不定时分享技术,资料,思考等文章!


                                   【技术服务】,详情点击查看:https://mp.weixin.qq.com/s/PtX9ukKRBmazAWARprGIAg 


      外包服务

       

    展开全文
  • 动态规划算法基本原理

    千次阅读 2013-11-28 23:09:47
    动态规划一般也只能应用于有最...动态规划算法分以下4个步骤: 1.描述最优解的结构 2.递归定义最优解的值 3.按自底向上的方式计算最优解的值 //此3步构成动态规划解的基础。 4.由计算出的结果构造一个最优解。 

    动态规划一般也只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解

    (对有些问题这个要求并不能完全满足,故有时需要引入一定的近似)。

    简单地说,问题能够分解成子问题来解决。

    动态规划算法分以下4个步骤:

    1.描述最优解的结构

    2.递归定义最优解的值

    3.按自底向上的方式计算最优解的值   //此3步构成动态规划解的基础。

    4.由计算出的结果构造一个最优解。   //此步如果只要求计算最优解的值时,可省略。

    好,接下来,咱们讨论适合采用动态规划方法的最优化问题的俩个要素:

    最优子结构性质,和子问题重叠性质。

    一、最优子结构。

    如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。

    意思就是,总问题包含很多歌子问题,而这些子问题的解也是最优的。

    二、重叠子问题。

    子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,

    有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,

    然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,

    从而获得较高的效率。

    ok,咱们马上进入面试题第56题的求解,即运用经典的动态规划算法:

    56.最长公共子序列。
    题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,
    则字符串一称之为字符串二的子串。

    注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。
    请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。
    例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,
    则输出它们的长度4,并打印任意一个子串。

    分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,

    因此一些重视算法的公司像MicroStrategy都把它当作面试题。

    步骤一、描述一个最长公共子序列

    先介绍LCS问题的性质:记Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}为两个字符串,

    并设Zk={z0,z1,…zk-1}是X和Y的任意一个LCS,则可得出3条性质:

    1.       如果xm-1=yn-1,那么zk-1=xm-1=yn-1,并且Zk-1是Xm-1和Yn-1的一个LCS;
    2.       如果xm-1≠yn-1,那么当zk-1≠xm-1时,Z是Xm-1和Y的LCS;
    3.       如果xm-1≠yn-1,那么当zk-1≠yn-1时,Z是X和Yn-1的LCS;

    下面简单证明一下由上述相应条件得出的这些性质:
    1.       如果zk-1≠xm-1,那么我们可以把xm-1(yn-1)加到Z中得到Z’,这样就得到X和Y的一个长度为k+1的公共子串Z’。

    这就与长度为k的Z是X和Y的LCS相矛盾了。因此一定有zk-1=xm-1=yn-1。
    既然zk-1=xm-1=yn-1,那如果我们删除zk-1(xm-1、yn-1)得到的Zk-1,Xm-1和Yn-1,显然Zk-1是Xm-1和Yn-1的一个公共子串,现在我们证明Zk-1是Xm-1和Yn-1的LCS。用反证法不难证明。假设有Xm-1和Yn-1有一个长度超过k-1的公共子串W,那么我们把加到W中得到W’,那W’就是X和Y的公共子串,并且长度超过k,这就和已知条件相矛盾了。
    2.       还是用反证法证明。假设Z不是Xm-1和Y的LCS,则存在一个长度超过k的W是Xm-1和Y的LCS,那W肯定也X和Y的公共子串,而已知条件中X和Y的公共子串的最大长度为k。矛盾。
    3.       证明同2。

    步骤二、一个递归解

    根据上面的性质,我们可以得出如下的思路:

    求两字符串Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}的LCS,

    如果xm-1=yn-1,那么只需求得Xm-1和Yn-1的LCS,并在其后添加xm-1(yn-1)即可(上述性质1);

    如果xm-1≠yn-1,我们分别求得Xm-1和Y的LCS和Yn-1和X的LCS,并且这两个LCS中较长的一个为X和Y的LCS(上述性质2、3)。

    根据上述结论,可得到以下公式,

    如果我们记字符串Xi和Yj的LCS的长度为c[i,j],我们可以递归地求c[i,j]:

              /      0                               if i<0 or j<0
    c[i,j]=          c[i-1,j-1]+1                    if i,j>=0 and xi=xj
             /       max(c[i,j-1],c[i-1,j]           if i,j>=0 and xi≠xj

    上面的公式用递归函数不难求得。自然想到Fibonacci第n项(本微软等100题系列V0.1版第19题)问题的求解中可知,

    直接递归会有很多重复计算,所以,我们用从底向上循环求解的思路效率更高。

    为了能够采用循环求解的思路,我们用一个矩阵(参考下文文末代码中的LCS_length)保存下来当前已经计算好了的c[i,j],

    当后面的计算需要这些数据时就可以直接从矩阵读取。

    另外,求取c[i,j]可以从c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三个方向计算得到,

    相当于在矩阵LCS_length中是从c[i-1,j-1],c[i,j-1]或者c[i-1,j]的某一个各自移动到c[i,j],

    因此在矩阵中有三种不同的移动方向:向左、向上和向左上方,其中只有向左上方移动时才表明找到LCS中的一个字符。

    于是我们需要用另外一个矩阵(参考下文文末代码中的LCS_direction)保存移动的方向。

    步骤三,计算LCS的长度

    LCS-LENGTH(X, Y)

     1 m ← length[X]
     2 n ← length[Y]
     3 for i ← 1 to m
     4      do c[i, 0] ← 0
     5 for j ← 0 to n
     6      do c[0, j] ← 0
     7 for i ← 1 to m
     8      do for j ← 1 to n
     9             do if xi = yj
    10                   then c[i, j] ← c[i - 1, j - 1] + 1
    11                        b[i, j] ← ""
    12                   else if c[i - 1, j] ≥ c[i, j - 1]
    13                           then c[i, j] ← c[i - 1, j]
    14                                b[i, j] ← ""
    15                           else c[i, j] ← c[i, j - 1]
    16                                b[i, j] ← ←
    17 return c and b

    此过程LCS-LENGTH以俩个序列X = x1, x2, ..., xmY = y1, y2, ..., yn〉为输入。

    它把c[i,j]值填入一个按行计算表项的表c[0 m, 0 n] 中, 它还维护b[1 m, 1 n] 以简化最优解的构造。

    从直觉上看,b[i, j] 指向一个表项,这个表项对应于与在计算 c[i, j]时所选择的最优子问题的解是相同的。

    该程序返回表中 b and cc[m, n] 包含X和Y的一个LCS的长度。

    步骤四,构造一个LCS,

    PRINT-LCS(b, X, i, j)

     

    1 if i = 0 or j = 0
    2     then return
    3 if b[i, j] = ""
    4     then PRINT-LCS(b, X, i - 1, j - 1)
    5         print xi
    6 elseif b[i, j] = ""
    7    then PRINT-LCS(b, X, i - 1, j)
    8 else PRINT-LCS(b, X, i, j - 1)

    该过程的运行时间为O(m+n)。

     

    下面是简单的java实现

    import java.util.Random;

    public class LCS{
        public static void main(String[] args){

            //设置字符串长度
            int substringLength1 = 20;
            int substringLength2 = 20;  //具体大小可自行设置

            // 随机生成字符串
            String x = GetRandomStrings(substringLength1);
            String y = GetRandomStrings(substringLength2);

            Long startTime = System.nanoTime();
            // 构造二维数组记录子问题x[i]和y[i]的LCS的长度
            int[][] opt = new int[substringLength1 + 1][substringLength2 + 1];

            // 动态规划计算所有子问题
           for (int i = substringLength1 - 1; i >= 0; i--){
                for (int j = substringLength2 - 1; j >= 0; j--){
                    if (x.charAt(i) == y.charAt(j))
                        opt[i][j] = opt[i + 1][j + 1] + 1;                                
                    else
                        opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);        
                }
            }

     

     

    展开全文
  • 矩阵连乘——动态规划算法

    千次阅读 多人点赞 2019-07-25 11:26:21
    矩阵连乘——动态规划算法 目录 矩阵连乘——动态规划算法 预备知识 前言 问题 应用动态规划方法的步骤 按照步骤分析问题 步骤1:最有括号化方案的结构特征 步骤2:一递归求解方案 步骤3:计算最优代价 ...

    矩阵连乘——动态规划算法

    目录

    矩阵连乘——动态规划算法

    预备知识

    前言

    问题

    应用动态规划方法的步骤

    按照步骤分析问题

    步骤1:最有括号化方案的结构特征

    步骤2:一个递归求解方案

    步骤3:计算最优代价

    步骤4:构造最优解

    算法的核心代码

    举例验证算法

    算法复杂度分析

    算法的基本要素

    1、最优子结构

    2、重叠子问题

    3、备忘录方法

    闲聊时刻


    预备知识

    了解矩阵连乘相关算法的前提是了解矩阵相乘的规则,此处应该询问度娘。

    什么是矩阵连乘的括号化方案?举个例子来理解。

    设有四个矩阵A、B、C、D,它们的维数分别是:A=50*10、B=10*40、C=40*30、D=30*5,总共有五种完全加括号的方式,如下:(A((BC)D))、(A(B(CD)))、((AB)(CD))、(((AB)C)D)、((A(BC))D). 如果看到这里还不懂矩阵相乘的相关知识,那么你可以放弃了,这个算法不适合你。

    前言

    对于矩阵连乘问题可以有多种解决办法,例如穷举法、递归与分治法、动态规划等。顾名思义,穷举法即把所有情况一一列举出来然后进行比较,当矩阵数目越来越大时,显然该方法不现实。采用递归与分治的思想比穷举法的可行性更强,但是递归的同时会重复计算同一个子问题,因此该算法依然不够理想。该篇主要讲解用动态规划算法如何解决矩阵连乘问题。

    问题

    给定n个矩阵{A1,A2,…,An },其中Ai  与Ai+1  是可乘的,i=1,2,3,···,n-1. 如何确定计算矩阵连乘积的计算次序,使得依次次序计算矩阵连乘积需要的数乘次数最少?

    应用动态规划方法的步骤

    1. 刻划一个最优解的结构特征;

    2. 递归地定义最优解的值;

    3. 计算最优解的值,通常采用自底向上的方法;

    4. 利用计算出的信息构造一个最优解。

    按照步骤分析问题

    步骤1:最优括号化方案的结构特征

    我们用符号Ai·j  (i<=j)表示AiAi+1···Aj  乘积的结果矩阵,如果问题是非凡的,即i<j,那么为了对AiAi+1···Aj 进行括号化,我们就必须在某个AkAk+1之间将矩阵链划分开(k为i<=k<j之间的整数),也就是说我们首先计算矩阵Ai···kAk+1···j  ,然后再计算他们的乘积得到最终结果Ai···j  。现在问题就变成了对矩阵Ai···kAk+1···j 进行独立求解,并且要满足最优括号化方案,最后将子问题的最优解合并就可以得到问题的最优解。

    步骤2:一个递归求解方案

    令m[i,j]表示计算矩阵Ai···j  数乘次数的最小值,那么原问题的最优解——计算A1···n  所需的最低代价就是m[1,n]。i=j时不需要做任何标量乘法运算,所以m[i,i]=0.若i<j,利用步骤1中得到的最优子结构来计算m[i,j]。设矩阵Ai···j  的大小为pi-1×pi  ,那么Ai···kAk+1···j 相乘的代价为pi-1*pk*pj 。因此可得m[i,j]=m[i,k]+m[k+1,j]+p_{i-1}*p_k*p_j.  

    此递归公式假定最优分割点k是已知的,但实际上我们并不知道。不过,k只有j-i种可能的取值,即k=i,i+1,···,j-1.由于最优分割点必其中,我们只需要检查所有可能的情况,推到最优者即可。因此,AiAi+1···Aj  最小代价括号化方案的递归求解公式变为

    步骤3:计算最优代价

    注意到,我们需要求解的不同子问题的数目是相对较少的,这种子问题重叠的性质是应用动态规划的另一个标识。假定矩阵Ai 的规模为pi-1×pi 。它的输入是一个序列p=<p0,p1,···,pn >,其长度为p.length=n+1.过程用一个辅助表来保存m[i,j],用另一个辅助表s[1···n-1, 2···n]记录最优值相应的分割点k,这样我们就可以利用表s构造最优解。

    步骤4:构造最优解

    虽然步骤3中求出了计算矩阵链乘积所需的最少标量乘法运算次数,但并未直接指出如何进行这种最优代价的矩阵链乘法计算。表s记录了最优解所需的信息,即记录了所有的k值,通过查询s表即可得到最终的答案。

    算法的核心代码

    void MatrixChain(int *p, int n, int**m ,int**s)
    {
     	for(int i=1; i<= n; i++) m[i][i]=0; //最小的子问题,矩阵个数为1
     	for(int r= 2; r<= n; r++)  //r代表子问题的矩阵个数,从2到n
    	{
       	for(int i=1;i<=n-r+1; i++){  //分析n-r+1种情况
     		int j=i+r-1;
            m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//假设每次都从第i个矩阵后分开
     		s[i][j]=i;
     		for(int k=i+1;k<j;k++){  //讨论k的所有可能情况
     		int t= m[i][k]+m[k+1][j]+ p[i-1]*p[k]*p[j];
            if(t<m[i][j]) {m[i][j]=t; s[i][j]=k;}}}//选择数乘次数最小的情况,并将相关数据覆盖于表中的相应位置
        }
    }
    

    举例验证算法

    A1A2A3A4A5A6
    30*3535*1515*55*1010*2020*25

    例如:

    算法复杂度分析

    算法的主要计算量取决于算法中对r、i和k的三重循环。循环体内的计算量为O(1),而三重循环的总次数为O(n3  ),因此算法的计算时间上界为O(n3 ),算法所占用的空间显然为O(n2 ).

    算法的基本要素

    1、最优子结构

    矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。

    利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

    同一个问题可以有多种方式刻划它的最优子结构,有些表示方法的求解速度更快(空间占用小,问题的维度低)。

    2、重叠子问题

    递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。这种性质称为子问题的重叠性质。

    动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。

    3、备忘录方法

    矩阵连乘的备忘录方法

    备忘录方法为每个已经计算的子问题建立备忘录, 即保存子问题的计算结果以备需要时引用,从而避免了相同子问题的重复求解。

    算法MemoizedMatrixChain是解矩阵连乘最优计算次序问题的备忘录方法。

    #include <iostream>
    using namespace std;
    
    int MemoizedMatrixChain(int n, int** &, int ** &,int *);
    int LookupChain(int ,int ,int *,int** &, int ** &);
    
    int MemoizedMatrixChain(int n, int** &m, int ** &s,int *p)
    {
        for ( int i=0; i <= n-1; i++){  //初始化表格
            for ( int j = 0; j <= n-1; j++)
            {
                m[i][j] =0;
                s[i][j] =0;
            }
        }
        return LookupChain(1,n,p,m,s);
    };
        
    int LookupChain(int i,int j,int *p,int** &m, int ** &s)  // 动态规划算法的核心代码,与前面提到的MatrixChain相似
    {
        if (i == j) return 0;
        int u = LookupChain(i,i,p,m,s) + LookupChain(i+1,j,p,m,s) + p[i-1]*p[i]*p[j];
        s[i][j] = i;
        for (int k = i+1; k < j; k++) {
             int t = LookupChain(i,k,p,m,s) + LookupChain(k+1,j,p,m,s) + p[i-1]*p[k]*p[j];
             if (t < u) { u = t; s[i][j] = k;}
         }
        m[i][j] = u;
        return u;
    };
    
        
    int main()
    {
        int n=6;
        int p[]={30,35,15,5,10,20,25};
        int** m;
        int** s;
        m=new int*[n];  //声明m表
        for (int zz=0;zz<n;zz++)
        	m[zz]=new int[n];
        s=new int*[n];  //声明s表
        for (int ii=0; ii<n; ii++)
            s[ii]=new int[n];
        cout<<MemoizedMatrixChain(n,m,s,p)<<endl;  //输出最小数乘次数
        return 0;
    }
    

    运行结果:

     

    算法复杂度分析:与动态规划算法一样,备忘录算法耗时O(n3 )。m[i][j]这些记录项的初始化耗费O(n2 )时间,每个记录项只填入一次。每次填入时,不包括填入其他记录项的时间,共耗费O(n)时间。因此通过备忘录技术,直接递归算法的计算时间从O(2n )降低到O(n3 )。

    总之,为求解矩阵链乘法问题,我们既可以用带备忘录的自顶向下动态规划算法,也可以用自底向上的动态规划算法,时间复杂度均为O(n3 )。两种方法都利用了重叠子问题性质,通常情况下,自底向上动态规划算法会比自顶向下备忘算法快(都是O(n3 )时间,相差一个常量系数),因为自底向上算法没有递归调用的开销,表的维护开销也更小。

    闲聊时刻

    前几天看毕淑敏的书,在此跟大家分享一段话。

     

    人不是不可以怯懦和懒惰,但他不能把这些陋习伪装成高风亮节,不能由于自己做不到高尚,就诋毁所有做到了这些的人是伪善。你可以跪在泥里,但你不可以把污泥抹在整个世界的胸膛,并因此煞有介事地说到处都是污垢。

    展开全文
  • 算法-动态规划 Dynamic Programming--从菜鸟到老鸟

    万次阅读 多人点赞 2017-07-15 22:58:29
    前言最近在牛客网上做了几套公司的真题,发现有关动态规划(Dynamic Programming)算法的题目很多。相对于我来说,算法里面遇到的问题里面感觉最难的也就是动态规划(Dynamic Programming)算法了,于是花了好长时间...
  • 五大常用算法之二:动态规划算法

    万次阅读 2018-03-14 12:52:53
    动态规划算法一、基本概念 动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。二、基本思想与...
  • 动态规划算法求解0,1背包问题

    千次阅读 2015-05-11 21:14:05
    看看动态规划的四个步骤:对于动态规划算法,我们必须明确两个基本要素,这两个要素对于在设计求解具体问题的算法时,是否选择动态规划算法具有指导意义:
  • 图解动态规划的解题四步骤

    千次阅读 2020-04-02 20:36:44
    本文会以 House Robber 题目为例子,讲解动态规划题目的四个基本步骤动态规划的的四个解题步骤是: 定义子问题 写出子问题的递推关系 确定 DP 数组的计算顺序 空间优化(可选) 下面我们一步一步地进行讲解。 ...
  • 1、理解动态规划求解优化问题的典型步骤,以及动态规划算法求解计算问题的时间复杂度分析 2、熟练掌握利用动态规划算法求解一维、二维等典型优化问题,如斐波那锲数、拾捡硬币、连续子序列的最大值、矩阵的括号、0-1...
  • 进行算法设计的时候,时常有这样的体会:如果已经知道一道题目可以用动态规划求解,那么很容易找到相应的动态规划算法并实现;动态规划算法的难度不在于实现,而在于分析和设计—— 首先你得知道这道题目需要用动态...
  • 动态规划算法解题思路

    千次阅读 2020-09-14 09:42:55
    在做动态规划类题目时最大的感觉就是能够分析出这道题目需要用动态规划算法来解,却没有办法构建出解题步骤,看到别人的分析时候又感觉代码很简单但是自己却想不出。 其实这还是没有理解到动态规划算法基本思想。 ...
  • 动态规划算法的优化技巧

    千次阅读 2017-03-12 20:07:53
    动态规划算法的优化技巧福州第三中学 毛子青[关键词] 动态规划、 时间复杂度、优化、状态**[摘要] 动态规划是信息学竞赛中一种常用的程序设计方法,本文着重讨论了运用动态规划思想解题时时间效率的优化。全文分为...
  • 目录:算法分析与设计实验报告——0-1背包问题的动态规划算法实现一、 实验目的二、实验要求三、 实验原理、 实验过程(步骤)五、 运行结果六、实验分析与讨论七、实验特色与心得附件一 实验过程(步骤)附件二 运行...
  • 算法---动态规划算法

    千次阅读 2019-05-14 08:57:42
    决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。 二、基本思想与策略 基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解...
  • 当阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展,当段决策确定后,就组成一决策序列,因而也就确定了整个过程的一条活动路线,这问题看作是前后关联具有链状结构的 多阶段过程就称为...
  • 第一部分、什么是动态规划算法   ok,咱们先来了解下什么是动态规划算法。  动态规划一般也只能应用于有最...动态规划算法分以下4个步骤: 描述最优解的结构递归定义最优解的值按自底向上的方式计算最优解的值
  • Leetcode动态规划算法示例讲解

    千次阅读 2019-03-04 20:17:25
    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。动态规划经分解得到子问题往往不是互相独立的,有些子问题被重复计算了很多次。因此...
  • 数学之美——动态规划 今 年九月二十三日,Google、T-Mobile 和 HTC 宣布了第一款基于开源操作系统 Android 的 3G 手机,其中一重要的功能是利用全球卫星定位系统实现全球导航。这功能在其它手机中早已使用,...
  • 动态规划算法及代码

    万次阅读 2011-11-21 17:01:36
    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题。 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次...
  • 动态规划算法以及例题

    千次阅读 2014-04-18 11:18:42
    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题。 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。...
  • Java数据结构和算法——动态规划做题步骤详细总结

    千次阅读 多人点赞 2020-07-11 18:19:48
    文章目录动态规划题目类型动态规划解题步骤动态规划实例讲解硬币问题机器人路径问题青蛙跳石头问题 动态规划题目类型 1、计数: 有多少种方式走到右下角 有多少种方法选出k数使得和为Sum 2、求最大最小值: 从左上...
  • 五大常用算法之动态规划算法

    千次阅读 2013-10-05 09:41:10
    决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。 二、基本思想与策略  基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序...
  • 动态规划算法简介

    千次阅读 2011-09-25 21:48:09
    一、基本概念 ...一决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。 二、基本思想与策略  基本思想与分治法类似,也是将待求解的问题分解为若干
  • 五大常用算法之二: 动态规划算法1

    千次阅读 2018-03-08 21:59:23
    决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。二、基本思想与策略 基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,220
精华内容 13,288
关键字:

动态规划算法的四个基本步骤