精华内容
下载资源
问答
  • 动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。 什么是动态规划 动态规划(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)

     

    展开全文
  • 动态规划算法

    千次阅读 2016-12-26 20:49:05
    1. 动态规划算法动态规划:通过把原问题分解为相对简单的子问题来求解复杂问题。动态规划常常适用于有重叠子问题和最优子结构性质的问题。 算法总体思想 动态规划算法与分治法类似,其基本思想也是将待求解问题...

    1. 动态规划算法

    动态规划:通过把原问题分解为相对简单的子问题来求解复杂问题。动态规划常常适用于有重叠子问题最优子结构性质的问题。

    1. 算法总体思想
      • 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题
      • 与分治法的区别在于:适用于动态规划算法求解的问题,经分解得到的子问题往往不是互相独立的;若用分治法求解,则分解得到的子问题数目太多,导致最终解决原问题需指数时间, 原因在于:虽然子问题的数目常常只有多项式量级,但在用分治法求解时,有些子问题被重复计算了许多次
      • 如果可以保存已解决的子问题的答案,就可以避免大量重复计算,从而得到多项式时间的算法
      • 动态规划法的基本思路是:构造一张表来记录所有已解决的子问题的答案(无论算法形式如何,其填表格式是相同的)
    2. 算法的基本步骤
      • 找出最优解的性质(分析其结构特征)
      • 递归地定义最优值(优化目标函数)
      • 自底向上的方式计算出最优值
      • 根据计算最优值时得到的信息,构造最优解

    算法的基本要素:

    1. 最优子结构
      • 在分析问题的最优子结构性质时,所用的方法具有普遍性:首先假设由问题的最优解导出的子问题的解不是最优的;然后设法证明在该假设下可构造出比原问题最优解更好的解;通过矛盾法证明由最优解导出的子问题的解也是最优的
      • 解题方法:利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解
      • 最优子结构是问题能用动态规划算法求解的前提:同一个问题可以有多种方式刻划它的最优子结构,有些表示方法的求解速度更快(空间占用小,问题的维度低)
    2. 重叠子问题
      • 子问题的重叠性:采用递归算法求解问题时,产生的子问题并不总是独立的,有些子问题被反复计算多次,称为子问题的重叠性质
      • 动态规划算法的特点:对每一个子问题只求解一次,并将结果保存在一个表格中;当再次需要求解该子问题时,可以用常数时间查表得出结果;通常独立的子问题个数随问题的规模呈多项式增长;因此采用动态规划算法求解此类问题只需要多项式时间,因而解题效率较高
    3. 备忘录方法
      • 备忘录方法是动态规划算法的一种变形,它也用表格来保存已解决的子问题答案,以避免重复计算
      • 与动态规划的区别在于,备忘录方法的递归方式是自顶向下的
      • 备忘录方法的控制结构与直接递归方法的控制结构相同,区别在于备忘录方法为每个解过的子问题建立了备忘录,以备需要时查看,从而避免了相同子问题的重复求解

    2. 示例: 最长公共子序列

    问题描述:

    1. 子序列
      • 给定序列的子序列是在该序列中删去若干元素后得到的序列
      • 若:给定序列 X=x1,x2,,xn ,称:另一序列 Z=z1,z2,,zk X 的子序列,是指存在一个严格递增的下标序列:i1,i2,,ik,使得:对于所有 j=1,2,,k 有: zj=xij
      • 例如: Z=B,C,D,B 是$X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}
    2. 公共子序列
      • 给定:序列 X Y
      • 若:另一序列 Z :既是X的子序列,又是 Y 的子序列
      • 称:Z是序列 X Y的公共子序列
    3. 最长公共子序列(LCS)问题
      • 给定2个序列 X=x1,x2,,xm Y=y1,y2,,ym
      • 找出 X Y的一个最长公共子序列
    4. 问题分析
      • 要求找出“一个”而不是“唯一的”最长公共子序列
      • 公共子序列在原序列当中不一定是连续的
        图片名称

    动态规划求解LCS问题:

    1. 最长公共子序列问题具有最优子结构性质
      • 给定序列 X=x1,x2,,xm Y=y1,y2,,yn ,设它们的一个最长公共子序列为 Z=z1,z2,,zk ,则:
      • xm=yn ;则: zk=xm=yn ,且 Zk1 Xm1 Yn1 的LCS
      • xmyn zkxm ;则: Z Xm1 Y 的LCS
      • xmyn zkyn ;则: Z X Yn1 的LCS
      • 可见:LCS(X,Y) 包含了这2个序列的前缀子序列的LCS,因此:最长公共子序列问题具有最优子结构性质
    2. 定义递归解(分析子问题的递归结构)
      • 由LCS问题的最优子结构性质可知:为求解 X Y 的一个LCS
      • xm=yn 时,须找出LCS( Xm1 , Yn1 ),然后将 xm (或 yn )添加到这个LCS上得到LCS( X , Y)
      • xmyn 时,须解决如下两个子问题:找出一个LCS( Xm1 , Y )和一个LCS(X, Yn1 )
      • 由此递归结构可以看出LCS问题具有重叠子问题性质:因为LCS( Xm1 , Y )和LCS(X, Yn1 )都包含一个公共子问题,即求解LCS( Xm1 , Yn1 )
    3. 建立递归关系(递归地定义最优值)
      • c[i][j] 表示序列 Xi Yj 的最长公共子序列的长度,其中: Xi= { x1,x2,,xi }; Yj= { y1,y2,,yj },若其中一个序列长度为0( i=0或j=0 ),则LCS的长度也是0
      • 根据最优子结构性质建立递归关系如下:
        图片名称
    4. 计算LCS的长度(最优值)
      • 子问题空间分析:总共 Θ(mn) 个不同的子问题,所以子问题空间不大,因此考虑采用动态规划法自底向上计算最优值
      • 设置两个数组作为输出:用 c[i][j] 表示序列 Xi Yj 的最长公共子序列的长度,问题的最优值记为 c[m][n] ,即LCS(X,Y)的长度。用 b[i][j] 记录 c[i][j] 是从哪一个子问题的解得到的,数组b用于构造最长公共子序列(最优解)
      • 按照b[i][j]的值表示的方向往回搜索: b[i][j]=1 :表示从左上方 c[i1][j1] 得到; b[i][j]=2 :表示从上方 c[i1][j] 得到; b[i][j]=3 :表示从左方 c[i][j1] 得到
      • 示例如下:
        图片名称

    代码:

    def lcs(a, b):
        lena = len(a)
        lenb = len(b)
        c = [[0 for i in range(lenb + 1)] for j in range(lena + 1)]
        flag = [[0 for i in range(lenb + 1)] for j in range(lena + 1)]
        for i in range(lena):
            for j in range(lenb):
                if a[i] == b[j]:
                    c[i + 1][j + 1] = c[i][j] + 1
                    flag[i + 1][j + 1] = 'ok'
                elif c[i + 1][j] > c[i][j + 1]:
                    c[i + 1][j + 1] = c[i + 1][j]
                    flag[i + 1][j + 1] = 'left'
                else:
                    c[i + 1][j + 1] = c[i][j + 1]
                    flag[i + 1][j + 1] = 'up'
        return c, flag
    
    
    def printLcs(flag, a, i, j):
        if i == 0 or j == 0:
            return
        if flag[i][j] == 'ok':
            printLcs(flag, a, i - 1, j - 1)
            print a[i - 1]
        elif flag[i][j] == 'left':
            printLcs(flag, a, i, j - 1)
        else:
            printLcs(flag, a, i - 1, j)
    
    
    a = 'ABCBDAB'
    b = 'BDCABA'
    c, flag = lcs(a, b)
    
    for i in c:
        print i
    print ''
    for j in flag:
        print(j)
    print ''
    
    printLcs(flag, a, len(a), len(b))
    print ''

    3. 示例: 最大子段和

    问题描述:

    • 给定n个整数(可能为负数)组成的序列a1,a2,…,an
    • 求该序列形如下式的子段和的最大值: maxjk=iak
    • 当所有整数均为负整数时定义其最大子段和为0
    • 依次定义,所求的最优值为: max{0,max1ijnjk=iak}
    • 例如: (a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2),该序列的最大子段和为20

    算法设计:

    • 通过对分治算法的分析可知,若记: b[j]=max1ij{jk=ia[k]}(ijn)
    • 则所求的最大子段和为: max1ijnjk=ia[k]=max1jn(max1ijjk=ia[k])=max1jnb[j]
    • b[j] 的定义可知:当 b[j1]>0 时: b[j]=b[j1]+a[j] ;否则: b[j]=a[j]
    • 由此可得 b[j] 的动态规划递归式: b[j]=max { b[j1]+a[j],a[j] } 1jn
    • 时间复杂度: On

    代码:

    int MaxSum (int n, int *a) {
        int sum = 0, b = 0;
        for(int i=1; i<=n; i++){
            if(b > 0)
                b += a[i];
            else
                b = a[i];
            if(b > sum)
                sum = b;
        }
        return sum;
    }

    4. 示例: 0-1背包问题

    问题描述:

    1. 给定:n种物品和一个背包
      • 物品 i 的重量是 wi,其价值为 vi
      • 背包的容量为:Capacity
    2. 约束条件:
      • 对于每种物品,旅行者只有两种选择:放入或舍弃
      • 每种物品只能放入背包一次
    3. 问题:如何选择物品,使背包中物品的总价值最大?

    递归定义最优值:

    1. 设所给0-1背包问题的子问题的最优值为: m(ic)
      • 即: m(ic) 是如下0-1背包问题的最优值:背包容量为 c,可选择物品为{ ii+1n }
      • 显然: 0-1背包问题具有最优子结构性质
    2. 根据最优子结构性质可以建立如下递归式:

    图片名称

    算法示例:
    下表是至底向上,从左到右生成的。其中,第5行表示只有第5个物品时,背包容量不同的情况下所对应的最大总价值;第4行表示有4,5两个可选物品时的背包最大总价值。

    图片名称

    用子问题定义状态:即f[i][c]表示前i件物品恰放入一个容量为c的背包可以获得的最大价值。则其状态转移方程便是:

    max(f[i-1][c], f[i-1][c-w[i]]+v[i])

    这个式子表示,在前i件物品放进容量c的背包时,考虑两种情况

    • 第一种是第i件不放进去,这时所得价值为:f[i-1][c]
    • 第二种是第i件放进去,这时所得价值为:f[i-1][c-w[i]]+v[i],就是如果第i件放进去,那么在容量c-w[i]里就要放进前i-1件物品,得到在容量c-w[i]的情况下,放进前i-1件物品的最大价值再加上第i个物品的价值,就是放进前i件物品的最大价值。

    最后比较第一种与第二种所得价值的大小,哪种相对大,f[i][c]的值就是哪种。

    完整代码如下:

    capacity = 10
    w = [4, 5, 6, 2, 2]
    v = [6, 4, 5, 3, 6]
    
    f = [[-1 for i in range(capacity+1)] for j in range(len(w))]
    
    
    def get_f(i, c):
        if i == 0:
            return v[i] if w[i] <= c else 0
        else:
            if c >= w[i]:
                return max(f[i-1][c], f[i-1][c-w[i]]+v[i])
            else:
                return f[i-1][c]
    for c in range(capacity+1):
        for i in range(len(w)):
            f[i][c] = get_f(i, c)
    
    print f
    展开全文
  • 动态规划算法介绍

    千次阅读 2019-02-17 19:34:49
    动态规划算法及其应用 动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法。动态规划算法的思想和分治算法类似,基本思想也是将待求问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原...

    动态规划算法及其应用

    动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法。动态规划算法的思想和分治算法类似,基本思想也是将待求问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。因此,动态规划算法是自底向上进行计算的,每一个子问题可以看成是一个状态,关键是找到状态转移方程,这样才能从子问题一步步推得原问题的解。

    具体的动态规划算法是多种多样的,不同的问题所设计出的动态规划算法都不同。但设计动态规划算法的步骤确是相同的,使用动态规划的基本设计思想设计算法解决最优化问题通常包含以下几个步骤:

    1. 找出最优解的性质,并刻画结构特征。
    2. 递归定义最优值。
    3. 以自底向上的方式计算最优值。
    4. 根据计算最优值时得到的信息,构造最优解。

     

    应用一:矩阵连乘问题:

    对于一个任意的矩阵相乘的链,我们该如何确定矩阵的相乘顺序,即如何加括号,使得矩阵链连乘的数乘次最少?

    求解过程:

    假设有我们需要计算一个矩阵链,矩阵链为 ,对于计算这么一个问题,先要它的子问题是什么,对于这么一个矩阵链连乘的问题,必然存在着一个性质:我们肯定会将矩阵链分割为两个部分,先计算左边的部分的矩阵连乘的结果,再计算右边的部分的矩阵连乘的结果,然后再将左边的部分和右边的部分相乘。那么如何描述将矩阵链分为左右两个部分,我们引入断点的概念,若矩阵链Ak 处断开,那么原问题就变成了 ,继而再计算左右两部分分别如何加括号。

    所以根据上面的分析,最优解的子问题结构的特征为计算A[i,j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。

    建立递归关系:设计算A[i:j], ,所需要的最少数乘次数为m[i,j],原问题的最优值为m[1,n]。

    , ,因此,

    时, ,这里 的维数为

     

    因此我们我们可以编写以下程序:

    矩阵链连乘的测试用例为A1(30*35),A2(35*15),A3(15*5),A4(5*10),A5(10*20),A6(20*25),使用MatrixChainOrder()函数确定矩阵链连乘的最小数乘次数,再将记录记录最小数乘次数的数组m进行打印,以及打印记录最佳断点的数据s,最后使用traceback()函数确定连乘顺序。

    最后通过打印的测试结果正确。

     

    #include<iostream>

    #include<iomanip>

    using namespace std;

    void MatrixChainOrder(int s[7][7],int m[7][7],int p[],int n){

         int i,j,k,t,r;

         for(i=1;i<=n;i++){

              m[i][i] = 0;

         }

         for(r=1;r<=n-1;r++){

              for(i=1;i<=n-r;i++){

                   j = i + r;

                   m[i][j] = m[i][i] + m[i+1][j] + p[i-1] * p[i] * p[j];

                   s[i][j] = i;

                   for(k=i+1;k<j;k++){

                        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;

                        }

                   }

              }

         }

    }

    void traceback(int s[7][7],int i,int j){

         if(i==j) return;

         traceback(s,i,s[i][j]);

         traceback(s,s[i][j]+1,j);

         cout << "Multiply A" << i << "," << s[i][j] << " and A" << s[i][j]+1 << "," << j << endl;

    }

    int main(){

         int n = 6;

         int p[7] = {30,35,15,5,10,20,25};

         int s[7][7];

         int m[7][7];

         int i,j;

         MatrixChainOrder(s,m,p,n);

         for(i=1;i<=6;i++){

              for(j=1;j<=6;j++){

                   if(j<=i) cout << "      ";

                   else cout << setw(5)  << m[i][j] << " ";

              }

              cout << endl;

         }

         for(i=1;i<=6;i++){

              for(j=1;j<=6;j++){

                   if(j<=i) cout << "      ";

                   else cout << setw(5)  << s[i][j] << " ";

              }

              cout << endl;

        }

        traceback(s,1,6);

        return 0;

    }

     

     

    结果为下:

     

     

    应用二:分糖果问题:

    There are N children standing in a line. Each child is assigned a rating value.

    You are giving candies to these children subjected to the following requirements:

    • Each child must have at least one candy.
    • Children with a higher rating get more candies than their neighbors.

    What is the minimum candies you must give?

     

    求解过程:

    题目的约束条件:每个孩子至少一个糖果,若孩子的value比邻接孩子的value高,那么这个孩子的糖果数一定比邻接孩子的糖果数目多。

    对于n个孩子的原问题,可以转化为先解决n-1个孩子的分糖果问题,在这基础上,在队尾加上一个孩子,然后再对糖果分配进行一定修改。因此前1个孩子为状态1,前2个孩子为状态2,前3个孩子为状态3,以此类推,可以由状态i推得状态i+1,最终得到n个孩子的分糖果问题。

    因为每个孩子至少有一个糖果,因此我们先对每个孩子分配一个糖果。然后先考虑前2个孩子,前2个孩子,前3个孩子,以此类推。

    考虑前i个孩子的时候,如果第i个孩子的value比第i-1个孩子的value值高,那么第i个孩子的糖果比第i-1个孩子的糖果多一个。

    如果第i个孩子的value比第i-1个孩子的value值低,那么第i个孩子的糖果为1。但考虑到第i-1个孩子的糖果也可能只有1个,这么做会出错。因此,若第i-1个孩子的value值比第i个孩子高,那么修改第i-1个孩子的糖果比第i个孩子多一个。再判断第i-2个孩子的value是否比第i-1个孩子的value高,若是,则第i-2个孩子的糖果值比第i-1个孩子的糖果值多一个。接着考虑第i-3,i-4,i-5,……个孩子,直到第j-1个孩子的value小于等于第j个孩子为止。

    根据以上思路,我们可以编写得到程序:

          

     

    class Solution {

    public:

        int candy(vector<int> &ratings) {

             int len = ratings.size();

             int i;

             int j;

             int total = 0;

             int flag = 0;

             int min;

             int max;

             vector<int> num(len, 1);

             for (i = 1; i <= len - 1; i++) {

                 if (ratings[i] > ratings[i - 1]) {

                      num[i] = num[i - 1] + 1;

                 }

                 else {

                      if (num[i - 1] >= 2) num[i] = 1;

                      else {

                          num[i] = 1;

                          for (j = i - 1; j >= 0; j--) {

                              if (ratings[j] > ratings[j + 1] && num[j] <= num[j + 1]) num[j] = num[j] + 1;

                              if (ratings[j] <= ratings[j + 1]) break;

                          }

                      }

                 }

             }

             for (i = 0; i <= len - 1; i++) {

                 total = total + num[i];

             }

             return total;

        }

    };

     

     

     

     

     

     

    应用三:字符串拆分问题

    Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

    For example, given
    s ="leetcode",
    dict =["leet", "code"].

    Return true because"leetcode"can be segmented as"leet code".

    求解过程:

    本题的解决思路为从字符串左边开始扫描,由于是从左边开始扫描,因此,在扫描的过程中,每一次扫描都可以看成一个状态。

    当扫描的位置达到字符串s的第i个位置时,我们就判断字符串的0到i的字符串是否能够进行拆分。此次拆分成功的问题可能分解为上次拆分成功的问题加上上次拆分成功后新的起始位置到现在位置的字符串是否能匹配到dict。例如题目中的例子,leetcode能够成功拆分,必然时先leet成功进行拆分,然后code也能进行成功拆分。

    我们使用一个数组a[]记录字符串s的扫描位置到达i时,子字符串0-i是否能够进行拆分,若能,则a[i]=true,若不能, a[i]=false。

    根据上述分析,我们可以编写程序如下:

     

    class Solution {

    public:

        bool wordBreak(string s, unordered_set<string> &dict) {

             int i = 1;

             int j;

             int len = s.length();

             bool a[len + 1];

             for (int q = 0; q <= len; q++) a[q] = false;

             a[0] = true;

             for (; i <= len; i++) {

                 for (j = 0; j < i; j++) {

                      if (a[j] == true) {

                          if (dict.find(s.substr(j, i - j)) != end(dict)) {

                              a[i] = true;

                          }

                      }

                 }

             }

             return a[len];

        }

    };

     

     

     

    展开全文
  • 文章目录1.序2.动态规划的基本概念[^1]3.动态规划算法的基本思想[^2]4....这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。...

    1.序

    近期笔者会写一些博客,与大家共同讨论一些经典的算法思想。这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。

    2.动态规划的基本概念[^1]

    在学习动态规划之前,先思考这样一个问题:什么是动态规划?为什么叫动态规划?
    当读者在试图探索这个问题的时候,不可避免的要了解动态规划的产生背景。动态规划是由 Dynamic Programming 翻译过来的。动态规划的概念是由美国数学家R.E.Bellman等人提出的,应用于工程领域。
    动态规划是是求解多阶段决策过程(decision process)的最优化问题一种方法。

    所谓多阶段决策过程是指这样一类决策过程:它可以把一一个复杂问题按时间(或空间)分成若干个阶段,每个阶段都需要作出决策,
    以便得到过程的最优结局。由于在每阶段采取的决策是与时间有关的而且前一阶段采取的决策如何,不但与该阶段的经济效果有关,
    还影响以后各阶段的经济效果,可见这类多阶段决策问题是一个动态的问题,因此,处理的方法称为动态规划方法。然而,动态
    规划也可以处理一些本来与时间没有关系的静态模型,这只要在静态模型中人为地引入“时间”因素,分成时段,就可以把它看作
    是多阶段的动态模型,用动态规划方法去处理。
    

    简言之,多阶段决策过程是指这样的一类特殊的活动过程:问题可以按时间顺序分解成若干相互联系的阶段,在每一个阶段都要做出决策,全部过程的决策是一个决策序列。
    下面举例说明什么是多阶段决策问题。
    例1(最短路线问题)在线路网络图1中,从A至E有一批货物需要调运。图上所标数字为各节点之间的运输距离,为使总运费最少,必须找出一条由A至E总里程最短的路线。
    在这里插入图片描述

    图1

    为了找到由A至E的最短线路,可以将该问题分成A—B—C—D—E 4个阶段,在每个阶段都需要作出决策,即在A点需决策下一步到B1还是到B2或B3;同样,若到达第二阶段某个状态,比如B1 ,需决定走向C1还是C2 ;依次类推,可以看出:各个阶段的决策不同,由A至E的路线就不同,当 从某个阶段的某个状态出发作出一个决策,则这个决策不仅影响到下一个阶段的距离,而且直接影响后面各阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策,使这些决策序列所决定的一条路线对应的总路程最短。

    3.动态规划算法的基本思想[^2]

    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题。
    在这里插入图片描述

    图2

    但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。
    如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
    在这里插入图片描述

    图3

    4.动态规划的求解步骤[^2]

    a. 找出最优解的性质,并刻划其结构特征。
    b. 递归地定义最优值。
    c. 以自底向上的方式计算出最优值。
    d. 根据计算最优值时得到的信息,构造最优解

    5.动态规划算法的基本要素[^2]

    5.1 最优子结构

    • 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质
    • 在分析问题的最优子结构性质时,所用的方法具有普遍性:首先假设由问题的最优解导出的子问题的解不是最优的,然后再设法说明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾。
    • 利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

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

    5.2 重叠子问题

    • 递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
    • 动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。
    • 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间,从而获得较高的解题效率。
      在这里插入图片描述
      图4

    6.一些经典的动态规划问题

    题目描述:
    给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

    示例 1:

    输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。
    

    示例 2:

    输入: "cbbd"
    输出: "bb"
    

    分析:
    一个问题要使用动态规划求解,一定要满足【最优子结构】,只有满足最优子结构,才能通过子问题的解 构造出 整个问题的解。

    在编码时,一般采用【备忘录】或 dp table来实现。
    最关键的要找出:该问题的递推关系式(状态转移方程)

    假设dp[i][j]=true,表示字符串s从s[i]到s[j]的子串为最长回文子串
    反之false.

    考虑 abcba 这个示例。如果我们已经知道 bca 是回文,那么要判断 abcba 是不是回文串,只需判断它的左首字母和右尾字母是否相等。这里左=右=a,因此abcba 是回文串

    从这里我们可以归纳出状态转移方程
    dp[i][j] = true
    前提是
    dp[i+1][j-1]为true,且 s[i] == s[j]

    #include <iostream>
    using namespace std;
    class MySolution {
    public:
        string longestPalindrome(string s) {
    
            int len = s.size();
            if (len < 2)
                return s;
            //bool dp[len][len];
            bool** dp;
            dp = new bool* [len];
            for (int i = 0; i < len; i++)
                dp[i] = new bool[len];//分配了len行len列的二维数组空间
        
            int max_len=1;//最大回文串长度
            int max_left;//最长回文串的起始位置
            for (int j = 0; j < len; j++)
            {
                for (int i = 0; i < j; i++)
                {
                    if (s[j] != s[i])
                        dp[i][j] = false;
                    else if (j - i < 3) // (j-1)-(i+1)+1< 2 即表明dp[i][j]是回文串
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];//s[i]==s[j]
                    if (j - i + 1 > max_len && dp[i][j])
                    {
                        max_len = j - i + 1;
                        max_left = i;
                    }
    
                }
            }
            return s.substr(max_left, max_len);
            // 用完要释放:
            for (int i = 0; i < len; i++)
            {
                delete[] dp[i]; 
                delete[]dp;
            }   
        }
    };
    int main()
    {
        MySolution sl;
        string s = sl.longestPalindrome("abcdedcabcdefggfedcba");
        cout << s << endl;
    }
    

    参考文献
    [1] 引用自百度文库https://wenku.baidu.com/view/c0f9fb156c175f0e7cd1377d.html
    [2]引用自老师的课件

    展开全文
  • 动态规划算法的优化技巧,使用动态规划方法解题,对于不少问题具有空间耗费大、时间效率高的特点,因此人们在研究动态规划解题时更多的注意空间复杂度的优化,运用各种技巧将空间需求控制在软硬件可以承受的范围之内...
  • 动态规划算法详解

    千次阅读 2016-07-17 17:12:38
    动态规划的介绍 动态规划一般也只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,故有时需要引入一定的近似)。简单地说,问题能够分解成子问题来...
  • 进行算法设计的时候,时常有这样的体会:如果已经知道一道题目可以用动态规划求解,那么很容易找到相应的动态规划算法并实现;动态规划算法的难度不在于实现,而在于分析和设计—— 首先你得知道这道题目需要用动态...
  • 五大常用算法之二:动态规划算法

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

    2019-08-09 00:12:31
    最近遇到动态规划算法的频率有点大,所以借此机会好好的来了解和学习一下动态规划。当然也记录下来,一起交流。 1. 了解概念 动态规划,英文名:Dynamic Programming ,简称DP,小名动规。 动态规划思想就是,...
  • 动态规划算法的基本要素

    千次阅读 2020-05-06 09:01:35
    问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。 在动态规划算法中,利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。 重叠子问题 可用动态规划...
  • 矩阵连乘积问题 动态规划算法动态规划动态规划问题的特征动态规划法的步骤矩阵连乘积问题分析动态规划法 求解分析最优解结构建立递归关系计算最优值算法计算矩阵连乘积的动态规划算法构造最优解 动态规划 动态规划...
  • 动态规划算法——知识点总结

    千次阅读 多人点赞 2017-05-15 10:03:49
    动态规划算法通常用于求解具有最优性质的问题 动态规划的算法设计: 1:找出最优解的性质,并描述其结构特征 2:递归定义最优值 3:以自底向上的方式计算最优值 4:根据计算最优值时得到的信息构造出最优解
  • 常见动态规划算法问题策略分析

    千次阅读 2016-05-28 13:34:37
    本文总结了几种常见动态规划算法的分析策略,但不做案例的具体分析,阅读前最好对这几种算法有一定基础了解。
  • 算法分析与设计实验报告——0-1背包问题的动态规划算法实现 目录:算法分析与设计实验报告——0-1背包问题的动态规划算法实现一、 实验目的二、实验要求三、 实验原理四、 实验过程(步骤)五、 运行结果六、实验分析...
  • 首先,本博客为原创作品,欢迎指导,随意转载,如果可以请转载时说明出处,附上...动态规划算法的基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题...
  • C++动态规划算法

    千次阅读 2019-04-28 15:49:50
    动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划(DP)。 基本思想与策略 基本思想与分治法...
  • 动态规划算法实现

    千次阅读 2009-06-08 15:03:00
    动态规划算法说明:最优化原理 1951年美国数学家R.Bellman等人,根据一类多阶段问题的特点,把多阶段决策问题变换为一系列互相联系的单阶段问题,然后逐个加以解决。一些静态模型,只要人为地引进“时间”因素,...
  • 算法---动态规划算法

    千次阅读 2019-05-14 08:57:42
    动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。 二、基本思想与策略 基本思想与分治法...
  • 题目:动态规划特点及其应用 目录 §1动态规划的本质 §1.1多阶段决策问题 §1.2阶段与状态 §1.3决策和策略 §1.4最优化原理与无后效性 §1.5最优指标函数和规划方程 §2动态规划的设计与实现 §2.1动态规划的...
  • 动态规划算法入门---java版

    千次阅读 2017-03-09 21:33:18
    动态规划算法(后附常见动态规划为题及Java代码实现) 一、基本概念  动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化...
  • 动态规划_动态规划算法的优化技巧

    千次阅读 2007-06-11 20:53:00
    动态规划算法的优化技巧 福州第三中学 毛子青 [关键词] 动态规划、时间复杂度、优化、状态 [摘要] 动态规划是信息学竞赛中一种常用的程序设计方法,本文着重讨论了运用动态规划思想解题时时间效率的优化。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 34,686
精华内容 13,874
关键字:

动态规划算法特点