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


      外包服务

       

    展开全文
  • 进行算法设计的时候,时常有这样的体会:如果已经知道一道题目可以用动态规划求解,那么很容易找到相应的动态规划算法并实现;动态规划算法的难度不在于实现,而在于分析和设计—— 首先你得知道这道题目需要用动态...

    进行算法设计的时候,时常有这样的体会:如果已经知道一道题目可以用动态规划求解,那么很容易找到相应的动态规划算法并实现;动态规划算法的难度不在于实现,而在于分析和设计—— 首先你得知道这道题目需要用动态规划来求解。本文,我们主要在分析动态规划在算法分析设计和实现中的应用,讲解动态规划的原理、设计和实现。在很多情况下,可能我们能直观地想到动态规划的算法;但是有些情况下动态规划算法却比较隐蔽,难以发现。本文,主要为你解答这个最大的疑惑:什么类型的问题可以使用动态规划算法?应该如何设计动态规划算法?

                                                                                 动态规划第一讲——缓存与动态规划

    一、缓存与动态规划


    例一:有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?


    分析:很显然,这道题的对应的数学表达式是F(n)=F(n-1) + F(n-2);其中F(1)=1, F(2)=2。很自然的状况是,采用递归函数来求解:

    int  solution(int n){
    	if(n>0 && n<2) return n;
    	return solution(n-1) + solution(n-2);
    }
     
    
     
        如果我们计算F(10), 先需要计算F(9) F(8); 但是我们计算F(9)的时候,又需要计算F(8),很明显,F(8)被计算了多次,存在重复计算;同理F(3)被重复计算的次数就更多了。算法分析与设计的核心在于 根据题目特点,减少重复计算。  在不改变算法结构的情况下,我们可以做如下改进:
    
    int dp[11];
    int  solution(int n){
    	if(n>0 && n<2) return n;
    	if(dp[n]!=0) return dp[n];
    	dp[n] = solution(n-1) + solution(n-2);
    	return  dp[n];
    }
    这是一种递归形似的写法,进一步,我们可以将递归去掉:
    int  solution(int n){
    	int dp[n+1];
    	dp[1]=1;dp[2]=2;
    	for (i = 3; i <= n; ++i){
    		dp[n] = dp[n-1] + dp[n-2];
    	}
    	return  dp[n];
    }
    当然,我们还可以进一步精简,仅仅用两个变量来保存前两次的计算结果; 这个算法留待读者自己去实现

    例二:01背包问题

    有n个重量和价值分别为vector<int> weight, vector<int> value的物品;背包最大负重为W,求能用背包装下的物品的最大价值?

    输入:n =4 
    weight=2, 1, 3, 2
    value =3, 2, 4, 2
    W=5
    输出=7


    思考一:我们可以采用穷举法,列出n个物品的所有组合形式,从中选取符合条件的最大价值:

    采用穷举法,必然需要能够举出所有状态,不重不漏;而如何穷举,方法多种多样,我们的任务是要穷举有n个元素组成的所有子集。而穷举的方法主要有两种—— 递增式(举出1~100之内的所有数字, 从1到100);和分治式的穷举(例如举出n个元素的集合,包含两种—— 含有元素a和不含元素a的)。于是,我们基于穷举法得到背包问题的第一种算法—— 递归与分治。

    int rec(int i, int j){//从i到n号物品,选择重量不大于j的物品的最大价值
    	int res;
    	if(i==n){
    		res=0;
    	} 
    	else if(j< w[i]){
    		res = rec(i+1, j);
    	}
    	else{
    		res = max(rec(i+1, j), rec(i+1, j-w[i])+v[i]);
    	}
    	return res;
    }

    调用res(0, W), 即可得到结果. 时间复杂度O(2^n);我们来分析一下递归调用的情况。


    为了偷懒,最后一行没有画出来,但是注意红色的部分,我们会发现(3, 2)这个子问题被计算了两次,很显然,如果问题规模足够大,数据足够多样,这种重复计算导致的时间耗费将更多。


    改进:采用递归加缓存的策略
    此时,时间复杂度是O(nW); 代码就省略不写了。


    思考二:上文中的记忆化搜索,如果可以将递归变为循环,这就是动态规划,对应的数学表达式如下:
    dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i]);//对应的计算表格如下和程序如下:
    void solution(){
    	fill(dp[n], dp[n]+W, 0);
    	for (int i = n-1; i >= 0; --i){
    		for (j = 0; j <= W; ++j){
    			if(j < w[i]) dp[i][j] = dp[i+1][j];
    			else dp[i][j] = max(dp[i+1][j], dp[i+!][j-w[i]]+v[i]);
    		}
    	}
    	return dp[0][W];
    }

    思考三:递归形式的多样化


    我们刚才的递归计算,在i这个维度是逆向的,同样我们可以采用正向的DP。规定dp[i][j]表示前i号物品中能选出重量在j之内的最大价值,则有递推式
    dp[i][j] = max(dp[i-1][j] , dp[i-1][j-w[i]] + v[i]);

    思考四:我们是如何想到递归算法的?


    也许,DP算法的难度不在于告诉你这个题目需要用DP求解,然后让你来实现算法。而在于你首先得意识到这道题目需要用递归求解,这里我们通过分析上面的思考步骤来总结DP算法的典型特征:
    1>DP算法起源于DC—— 一个问题的解,可以先分解为求解一系列子问题的解,同时包含重叠子问题:于是,我们得到DP算法的第一个黄金准则:某个问题具有独立而重叠的字问题;子问题不独立,没法进行分治;子问题不重叠,没有进行DP的必要,直接用普通的分治法就可以了。
    2>DP算法黄金准则2: 最优子问题—— 子问题的最优解可以推出原问题的最优解。

    我们还是来看上面的那个决策树,很明显,DP的本质就在于缓存。我们寻找DP结果的时候,往往是需要遍历这个树,从中找出最优解。但是有些情况下,我们需要寻找的不是最优解,而是可行解,这个时候往往使用DFS或者循环更为有效,后面,我们会给出例子。此时,我们仅仅需要记得,动态规划的第二个条件—— 最优子问题。

    所以算法的设计思路不在于一下子就想到了某个问题可以使用DP算法,而在于先看能不能用穷举法,如果可以用问题可以分解,分治法+穷举可以解决;如果问题包含重叠字问题,并且是求解最优解,那么此时用动态规划。

    展开全文
  • 五大常用算法之二:动态规划算法

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

    动态规划算法

    一、基本概念

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


    二、基本思想与策略

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

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

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

     


    三、适用的情况

    能采用动态规划求解的问题的一般要具有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 }
    复制代码

     

    本文转自这里

    展开全文
  • 动态规划算法的优化技巧

    千次阅读 2017-03-12 20:07:53
    动态规划算法的优化技巧福州第三中学 毛子青[关键词] 动态规划、 时间复杂度、优化、状态**[摘要] 动态规划是信息学竞赛中一种常用的程序设计方法,本文着重讨论了运用动态规划思想解题时时间效率的优化。全文分为...
  • 动态规划算法——知识点总结

    千次阅读 多人点赞 2017-05-15 10:03:49
    动态规划算法通常用于求解具有最优性质的问题 动态规划的算法设计: 1:找出最优解的性质,并描述其结构特征 2:递归定义最优值 3:以自底向上的方式计算最优值 4:根据计算最优值时得到的信息构造出最优解
  • (该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势) 三、动态规划基本概念 状态:描述事物的性质,不同事物有不同的性质,因而用不同的状态来刻画。...
  • 第一部分、什么是动态规划算法   ok,咱们先来了解下什么是动态规划算法。  动态规划一般也只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,...
  • 算法---动态规划算法

    千次阅读 2019-05-14 08:57:42
    动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。 二、基本思想与策略 基本思想与分治法...
  • 利用动态规划算法,可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。 基本思想与原理 动态规划算法的基本思想是:将待求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到...
  • 动态规划算法秘籍

    2017-12-26 09:58:17
    动态规划是1957年理查德·贝尔曼在《Dynamic Programming》一书中提出来的,八卦一下,这个人可能有同学不知道,但他的一个算法你可能听说过,他和莱斯特·福特一起提出了求解最短路径的Bellman-Ford 算法,该算法...
  • 动态规划_动态规划算法的优化技巧

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

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

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

    千次阅读 2018-03-08 21:59:23
    非常有必要看一看:漫画:什么是动态规划?详解动态规划——邹博讲动态规划一、基本概念 动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多...
  • 1 回顾 2 你会学到什么 ... 4 动态规划入门 5 解决问题的方法 5-1 问题分析 5-2 暴力枚举 5-3 动态规划 5-4 算法思路 5-5 源码实现 5-6 模拟gif 6 算法评价 7 总结 8 GitChat 9 公众号
  • 浅谈路径规划算法

    万次阅读 多人点赞 2017-09-19 16:32:09
    1导言 1.1算法 1.2Dijkstra算法与最佳优先搜索 1.3A*算法 2启发式算法 2.1A*对启发式函数的使用 2.2速度还是精确度? 2.3衡量单位 2.4精确的启发式函数 2.4.1预计算的精确启发式函数 2.4.2线性精
  • 基础阶段(四)——MDP的动态规划算法 前言 一、pandas是什么? 二、使用步骤 1.引入库 2.读入数据 总结 前言 提示:这里可以添加本文要记录的大概内容: 例如:随着人工智能的不断发展,机器学习这门...
  • 转载:https://blog.csdn.net/qq_37763204/article/details/79394397?utm_source=distribute.pc_relevant.none-task-blog-baidujs-5 一、基本概念    动态规划是运筹学中用于求解决...
  • 五大常用算法——动态规划算法详解及经典例题

    万次阅读 多人点赞 2018-02-27 23:12:16
    一、基本概念 动态规划是运筹学中用于求解决策过程中的最优化数学方法。当然,我们在这里关注的是作为一种算法设计技术,作为一种使用多阶段决策过程最优的通用方法。 动态规划过程是:每次决策依赖于当前状态,又...
  • 动态规划算法通常用于求解具有某种最优性质的问题。动态规划算法与分治法类似,其基本思想都是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态...
  • 数学之美——动态规划 今 年九月二十三日,Google、T-Mobile 和 HTC 宣布了第一款基于开源操作系统 Android 的 3G 手机,其中一个重要的功能是利用全球卫星定位系统实现全球导航。这个功能在其它手机中早已使用,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,034
精华内容 12,013
关键字:

动态规划算法的必要条件