精华内容
下载资源
问答
  • 动态规划理论思想

    2016-04-30 17:54:08
    动态规划的理论思想还是不能够深入理解,于是就重新看了一下,并将其转载了过来 转自:http://blog.csdn.net/liuxucoder 终于讲到动态规划了~该来的总会来的…… 作为算法的一大核心,我大...



    动态规划的理论思想还是不能够深入理解,于是就重新看了一下,并将其转载了过来



    转自:http://blog.csdn.net/liuxucoder


    终于讲到动态规划了~该来的总会来的……

    作为算法的一大核心,我大动态规划的影响力不可谓不大。很多工业级的算法里,都清晰可见动态规划的模样。 
    你问我为何这么普及?道理很简单。丫的动态规划也是一种思想!!!

    相信刚开始学算法的同学都有过被贪心虐的死去活来的时候,那种策略的论证过程,有时明明就是只差一点点,但是就是做不出…… 
    如果你喜欢这种感觉,那么恭喜你,动态规划也是充斥着这种没着没落的感觉…… 如果你不喜欢~反正也上了算法这条贼船,多学点东西总是没坏处的~

    动态规划思想

    好了,不废话了。如果之前接触过贪心问题的话,对于问题的子问题化、分别求解和组合出最后结果的整个思想肯定不陌生。动态规划使用相同的思想,也是将待求解的问题分解为若干个子问题,按顺序求解子问题,同时前一子问题的解,为后一子问题的求解提供了有用的信息。

    1. 与贪心算法、分治法类似,在求解子问题时只保存针对当前子问题的最优解。
    2. 由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个数组中。
    3. 值得注意的是,适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)。

    动态规划适用条件

    既然说动态规划是一种思想,那么就要讨论下动态规划的成立条件。

    1. 总问题可划分为多个子问题。
    2. 通过子问题的最优解可以获得整个问题的最终最优解。
    3. 子问题必须具有无后效性。当前状态的子问题的解不会被之后状态的子问题影响。
    4. 动态规划的子问题不独立,单个子问题的最优解可以使用之前已解决的子问题的解,这也是动态规划的优点

    如果第四条对于一个问题不成立,那么这个问题的计算方法就退回到了一般的回溯法或者搜索问题,如果这个时候仍然使用动态规划进行求解,整个问题的求解并不会得到任何优化。

    动态规划一般步骤

    动态规划描述子问题一般使用“状态”这个词,选定子问题的某种性质作为“状态”。整个问题从最初状态开始,然后按照某种决策顺序依次解出对应状态的最优解,最后到达结束状态。整个决策的顺序需要根据问题进行调整。

    也就是说,动态规划的解题步骤可以一般性的划分为以下几种:

    1. 子问题的划分。 按照一定的顺序把整个问题划分为若干个规模相等的子问题。
    2. 子问题状态的确定。根据问题需求和子问题的各个属性确定子问题的”状态“,同时需要满足无后效性。
    3. 推导状态转移方程。 状态转移指的就是根据上一个状态(或者叫上一个子问题的解)来获取当前子问题解的过程。 如果要进行具体的计算,那么就需要写出具体的算式。这一步也是最需要时间的,传说中最考验功力的一关
    4. 边界条件和初始值的确定。由于动态规划是根据之前子问题的解来推导当前子问题的解,所以最初状态的值必须确定。边界条件是用来描述结束状态的,如果当前状态完全到达边界,便视为已经到达了最终状态。

    最重要的就是理解”状态“对于每个问题来说是哪一个性质。 
    一个子问题可能有多个状态,比如对于背包问题来说,子问题的性质就包括”当前重量“”当前体积“两个。但是单个子问题我们只能计算一个性质,也就是只能关注一个状态。

    应用举例

    额,先看个斐波那契数列的例子吧。 
    斐波那契数列的解法很多,搜索和分治法都可以解出,但是可以看到的是,如果给定的N比较大,那么搜索和分治都会变得很慢,甚至有溢出的问题出现。关键就在于这两种方法都没有保存子问题的解,而是会重复进行很多计算。 
    一旦出现重复的子问题求解,优先考虑动态规划方式求解,一般都会获得很多优化。 
    斐波那契的动态规划解法:

    1. 步骤划分。按照从1到n的顺序,每个整数都是一步,整个问题可以划分为n个子问题。
    2. 性质确定。整个子问题就一个性质”数值“,没有其他选择,那么a[k] (0 < k <= n)就指的是对于第K步对应的斐波那契数。
    3. 状态转移方程。 a[n] = a[n-1] + a[n-2],不解释。
    4. 边界值和起始值。由于这是一维的求解,所以边界值只有一个(0 < k <= n)。起始值最少需要两个:a[0] = 0,a[1] = 1。

    OK。现在我们就可以开始计算了,

    a[2] = a[1] + a[0];
    a[3] = a[2] + a[1];
    a[4] = a[3] + a[2];
    ......
    a[n] = a[n-1] + a[n-2]
    

    这样就可以显示出动态规划的优点所在:针对每一个状态只需要进行一次运算,之后就可以重复利用这个状态的值,从而减少了大量不必要的重复计算

    展开全文
  • 动态规划基本思想

    千次阅读 2018-07-04 11:24:38
    动态规划和分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 与分治法不同的是,动态规划法中分解得到的子问题不是互相独立的。若用分治法来解这类...

    基本要素:
    (1)最优子结构性质
    (2)重叠子问题性质
    思想:
    动态规划和分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
    与分治法不同的是,动态规划法中分解得到的子问题不是互相独立的。若用分治法来解这类子问题,分解得到的子问题数目非常多,最后解决原问题需要耗费指数时间。但是这些子问题有很多是相同的,也就是同一个子问题被计算了很多次,不同子问题的数量可能只有多项式量级。
    如果我们保存已经解决的子问题的解,需要解相同子问题时找出已经计算出的解,这样可以减少大量重复计算,最终得到多项式时间算法。
    经常用一个来记录所有已解决的子问题的解。不管该子问题以后是否被利用,只要它被计算过,就将其结果填入表中。这就是动态规划的基本思想。具体的动态规划算法多种多样,但它们具有相同的填表格式

    —(计算机算法设计与分析 第四版 王晓东)—
    ####动态规划例子:(矩阵连乘问题)
    给定N个矩阵{A1,A2,A3,An},其中Ai与A(i+1)是可以相乘的,考察这N个矩阵的连乘积A1A2,An。
    由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定,比如下面4个矩阵的连乘积。
    A1,A2, A3, A4
    1,(2,(3,4))
    1,((2,3),4)
    (1,2),(3,4)
    (1,(2,3)),4
    ((1,2),3),4

    #####最优解的结构
    计算A[1:n]的最优次序所包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的。
    A[1:n] = A[1:k] * A[K+1:n] 其中 ( 1 < k < n)
    递推关系如下:
    m(i , j) = 0 ,(i=j)
    m(i , j) = min{ m(i,k) + m(k+1,j) + P(i-1)P(k)P(j) } ,(i < j )
    #####重叠子问题
    重叠的子问题主要体现在m表格里,

    例题:我们计算如下6个矩阵的连乘积,
    A1 ------ A2 ------ A3 ----- A4 ----- A5 ----- A6
    (3035) (3515) (155) (510) (1020) (2025)

    const int N = 6;
    int table[N + 1][N + 1];
    int p[N + 1] = { 30, 35, 15, 5, 10, 20, 25 };
    void MatrixMulti()
    {
    	for (int r = 2; r <= N; r++) //r表示连乘矩阵的个数
    	{
    		for (int i = 1; i <= N - r + 1; i++) //i表示起始矩阵索引
    		{
    			int j = i + r - 1; //j表示终止矩阵索引
    			for (int k = i; k < j; k++)
    			{
    				int temp = table[i][k] + table[k+1][j] + p[i - 1] * p[k] * p[j];
    				table[i][j] = (table[i][j] == 0) ? temp : min(table[i][j], temp);
    			}
    		}
    	}
    }
    int main()
    {
    	MatrixMulti();
    	cout << "最小乘积为:" <<table[1][N] << endl;
    	return 0;
    }
    /*输出结果:
    最小乘积为:15125
    table数组内容为:
    0       0       0       0       0       0       0
    0       0       15750   7875    9375    11875   15125
    0       0       0       2625    4375    7125    10500
    0       0       0       0       750     2500    5375
    0       0       0       0       0       1000    3500
    0       0       0       0       0       0       5000
    0       0       0       0       0       0       0
    
    */
    
    展开全文
  • 动态规划思想总结

    千次阅读 2016-07-30 17:00:44
     动态规划是求解决策过程最优的数学方法,它的核心思想是把多阶段过程转化为一系列单阶段的问题,利用各阶段之间的关系,逐个求解。 二、动态规划大的分类: (1)线性动规;(2)区域动规;(3)树形动规;(4)...

    一、dp的思想及实现方法:

      动态规划是求解决策过程最优的数学方法,它的核心思想是把多阶段过程转化为一系列单阶段的问题,利用各阶段之间的关系,逐个求解。

    二、动态规划大的分类:

    (1)线性动规;(2)区域动规;(3)树形动规;(4)背包动规。

    三、动态规划的概念、意义

      动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法。不像搜索或数值计算那样,具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题,由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的设计方法对不同的问题,有各具特色的解题方法,而不存在一种万能的动态规划算法,可以解决各类最优化问题。因此读者在学习时,除了要对基本概念和方法正确理解外,必须 具体问题具体分析处理,以丰富的想象力去建立模型,用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论,逐渐学会并掌握这一设计方法。

      其中含有递推的思想以及数学中的加法原理,乘法原理。

    四、动态规划的基本思想

      动态规划算法通常用以求解具有某种最有性质的问题。这类问题可能存在许多可行解,每个节对应一个值,我们的目的通过这种思想找到最优解。其方法是通过想求解子问题,然后从这些子问题的解得到原问题的解。因此我们能够保存已经解决的子问题的答案,而在需要时再找出来已经求得的答案,这样可避免大量预算,节省时间。我们可以用一个表记录所有已经解决的子问题的答案。不管之后是否会用到,只要他被计算过,就将其结果填入表中。这就是动态规划的基本思路,虽然动态规划算法多种多样,但是他们具有相同的填表格式。

    五、基本概念

    1、多阶段

      通常一类活动过程可以分为若干个互相联系的阶段,每个阶段都需要作出决策(采取措施),一个阶段决策确定以后,常常影响到下一个阶段的决策,从而完全确定一个活动的路线,则称他为多阶段决策问题。

    2、动态规划问题中的术语

      阶段:把所有求解问题的过程恰当的分为果敢个相互联系的阶段,便与求解,过程不同,阶段数就不同。

      状态:表示每个阶段开始面临的自然状况或客观条件,成为不可控制的因素。

      无后效性:给定某一阶段的状态,这阶段之后的过程的发展不受不受之前的影响,多有阶段确定,整个过程将确定。过程的历史只能通过当前的状态去影响它的未来的发展。

      决策:给定一个状态,从该状态演变到下一个阶段的某个状态的一种选择成为决策。决策可表示为一个数或一组数,不同的决策对应不同的数值。因为满足无后效性,每个阶段选择决策时只需考虑当前的状态无需考虑历史状态。

      状态转移方程:给定k阶段状态变量x(k),若k+1阶段状态变量x(k+1)也确定下来,这就是状态转移的规律,称为状态转移方程。最优原理:作为整个过程的最优决策,他满足:相对前面的状态来说,余下的子策略必是最有子策略。

    六、基本模型

      (1)确定问题的决策对象。 (2)对决策过程划分阶段。 (3)对各阶段确定 状态变量。 (4)根据状态变量确定费用 函数和目标函数。 (5)建立各阶段状态变量的转移过程,确定状态转移方程。

     做

    展开全文
  • 动态规划出现在很多算法题目里面,初学者入门并不容易,网上很多文章看了以后还是不是很理解什么动态规划算法,就打算记录一下自己的笔记,用案例加详细说明的方式深入理解动态规划核心思想。 以lletcode198...

          动态规划出现在很多算法题目里面,初学者入门并不容易,网上很多文章看了以后还是不是很理解什么的动态规划算法,就打算记录一下自己的笔记,用案例加详细说明的方式深入理解动态规划的核心思想。

          以lletcode198题目为例(抢金店),不熟悉题目的同学可以百度一下~这是一个典型的动态规划类题目。

         首先看非动态规划怎么实现:

         

    public class Solution{
       public int rob(int[] nums){
          return slove(nums.length,nums);
       }
       public int slove(int idx,int[] nums){
          int max = Math.max(nums[idx]+slove(idx- 2,nums),solve(idx-1,nums));
          return max;
       }
    }

         上面的代码是通常的暴力搜索解法,这个一定要理解。本质上暴力搜索都是递归问题。说到这里,大家可能会问,怎么还没提到动态规划呢?

         我们仔细看上面的代码,会发现时间复杂度很高,为什么呢?   因为有大量的重复计算!做如下分析:

                   n  -> (n-2,n-3,n-4,......)         //n代表一开始抢第n家店,后面以此类推。。。

                   n-1    ->(n-3,n-4,.........

        这里,大家会发现,红色划线部分的店会重复计算,我们用动态规划就是希望去除冗余计算,降低时间复杂度。

       怎么做呢?基本步骤如下:

              1)设计暴力算法,找到冗余

              2)  设计并存储状态(一维,二维,三维,甚至Map)

             3) 递归式(状态转移方程)

             4)自低向上计算最优解

        一般的动态规划算法都需要以上流程,乍一看,写的啥,看不懂是吧,下面以这个题目为例详细解读这几个步骤,第一个步骤上面代码已经完成了,下面看第二步:之说以会重复计算,是因为我们没有保存已经计算过的店家,所有我们用一个中间状态来保留计算过的店家,以此防止重复计算,完整代码如下:

              

           

    public class Solution{
       public static int[] result;//记录中间态
       public int rob(int[] nums){
          result = new int[num.length-1];
          for(int i =0;i<num.length-1;i++){
                result[i] = -1;//初始化为,-1表示没有计算过
          } 
          return slove(nums.length,nums);
       }
       public int slove(int idx,int[] nums){
          if(result[ids]>=0{

                        return result[idx];//大于0,表示该位置计算过了,直接返回,该行代码很关键

          }
          int max = Math.max(nums[idx]+slove(idx- 2,nums),solve(idx-1,nums));
          return max;
       }
    } 

              以上代码中,红色部分为第二部。设计了一个中间状态,好好体会吧~

             下面看第三部代码:

       max = Math.max(nums[idx]+slove(idx- 2,nums),solve(idx-1,nums));

            状态转移方程就是一个递归式。

            到这里,应该理解了动态规划的核心啦,做一个小总结:

                1)思考过程为:原问题->子问题->原问题   的过程
                2) 去冗余,空间换时间

             

           



    展开全文
  • 动态规划——基本思想

    万次阅读 2016-07-14 15:08:10
    动态规划——基本思想动态规划的特点 把原始问题划分为一系列子问题 求解每个子问题仅一次,并将其结果保存在一个表中,以后用到时到时直接存取,不重复计算,节省计算时间 自底向上地计算 使用范围 一类优化问题:...
  • 动态规划算法思想解决找零钱问题

    万次阅读 2017-10-16 14:20:54
    前言  关于找零钱问题,网上已经有很多相关的资料以及优秀的文章博客等。这里写这篇博客的初衷很简单,就是为了方便自己,回过头来捡起这个知识能快一点,接受起来更易理解点;... 动态规划(dynamic progr...
  • 以往见过许多教材,对动态规划(DP)的引入属于“奉天承运,皇帝诏曰”式:不给出一点引入,见面即拿出一大堆公式吓人;学生则死啃书本,然后突然顿悟。针对入门者的教材不应该是这样的。 现在,我们试着自己来一...
  • 动态规划问题思想及算法

    千次阅读 2019-03-27 15:50:05
    通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量: 一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的...
  • 动态规划算法思想的一些理解

    千次阅读 2016-05-11 16:28:40
    动态规划算法思想和分治法的思想是类似的,都是将问题的规模缩小,然后求解子问题,根据子问题来解决总问题,但是分治算法的子问题之间是相互独立的,因此在对子问题的求解过程中就产生了很多重复的计算,递归就是...
  • 动态规划:一个模型(多阶段决策最优解模型),三个特征(最优子结构、无后效性和重复子问题),适用于求解最优问题。本文主要参考资料是王争的《数据结构与算法之美》,数据结构和算法作为程序员的...
  •  动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。 二、基本思想与策略  基本思想与分治...
  • 动态规划之一:基本思想

    万次阅读 2018-06-03 23:09:17
    基本思想一般来说,只要问题可以划分为规模更小的字问题,并且原问题的最优解中包含了子问题的最优解,则可以考虑用动态规划解决。动态规划的实质是分治思想和解决冗余。因此,动态规划是一种将问题实例分解为更小的...
  • 算法导论-----动态规划什么

    千次阅读 2016-12-14 21:41:20
    本文更像是一篇科普,方便理解什么是动态规划。一、动态规划概述  动态规划(Dynamic Programming)通常是用来解决最优化问题的。最初是由数学家在研究多阶段决策过程的优化问题时,提出的优化原理,把多阶段过程...
  • 五大算法思想 动态规划 矩阵连乘问题、走金字塔问题、最长公共子序列问题、最长递增子序列问题、0-1背包问题、完全背包问题
  • 动态规划算法

    千次阅读 2015-08-02 09:45:57
    动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。 二、基本思想与策略 基本思想与分治法...
  • 动态规划详解

    千次阅读 2020-02-17 15:36:36
    动态规划的基本思想就是把待解决的问题分成若干的子问题,并且前子问题的解能为后子问题的解提供基础(动态规划的子问题往往不是独立的)。 以我们熟悉的斐波拉契数列为例,递归的方法大家都明白,这个也可以用动态...
  • 什么是动态规划” , 用两个经典问题举例。

    万次阅读 多人点赞 2014-03-12 08:29:56
    1.什么是动态规划? 看了很多题解,一般解决者开始就说用DP来解,然后写了嵌套的for循环,不是很容易看懂,但是确实解出来了,我们这次来看下到底什么是动态规划?它有什么特点呢?容我抄一段话: 动态规划...
  • 动态规划算法详解

    千次阅读 2016-07-17 17:12:38
    动态规划的介绍 动态规划一般也只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,故有时需要引入一定的近似)。简单地说,问题能够分解成子问题来...
  • 动态规划入门

    千次阅读 2019-10-11 15:27:28
    动态规划入门
  • 动态规划 核心思想 将问题分解为多个子问题,求解出多个子问题的解,然后将子问题的解存储起来,这些子问题的解相互是有关系的所以一般用迭代来解决,最后将子问题的解合并得到最终问题的解。 一般有以下性质: 最...
  • 动态规划

    千次阅读 2014-07-16 16:22:02
    终于来到了算法设计思想中最难,也最有趣的这部分,在去年的google笔试中,7道算法设计题有2道动态规划(Dynamic Programming)。 看了这么久的算法,这部分也是唯一感觉到了比较难的地方, 从这篇文章开始,将花...
  • 动态规划初识

    千次阅读 2016-03-07 16:00:00
    初识动态规划引言:动态规划的理论性和实践性都比较强,一方面需要... 一、动态规划的基本思想: 求解具有某种最优性质的问题。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题
  • 编程核心思想概念

    千次阅读 2018-07-22 19:22:19
    编程核心思想和概念  开发一个程序或一个系统首先都要了解需要哪些输入,输出数据,中间会产生哪些数据,此即数据内容,  然后缝隙数据键的关系,形成数据模型,此即为数据结构,接着考虑数据在程序或系统中如何...
  • 数据结构和算法——动态规划

    千次阅读 2014-10-02 16:08:17
    一、动态规划思想 动态规划(dynamic programming)是一种算法设计的思想,主要是将一个问题划分成几个更小的问题,并对这样更小的问题进行求解,最终得到整个问题的解。有人在想这样的方式和分治法的求解很像。...
  • 动态规划总结

    万次阅读 2017-08-05 13:42:12
    终于来到了算法设计思想中最难,也最有趣的这部分,在去年的google笔试中,7道算法设计题有2道动态规划(Dynamic Programming)。看了这么久的算法,这部分也是唯一感觉到了比较难的地方,从这篇文章开始,将花连续...
  • matlab实现动态规划算法

    千次阅读 2020-09-18 16:19:11
    matlab实现动态规划算法论文例子实现算法代码 最近看缓存相关论文,里面提到...背包问题,讲解的通俗易懂,看懂后可以大致了解动态规划步骤,看懂后这种思想便可以移植到其他问题上。 论文例子 论文title《Mobility-Awa
  • 常见动态规划问题总结

    千次阅读 2017-04-12 19:35:34
    动态规划即Dynamic Programming,简称DP,初接触动态规划问题会觉得这类问题很抽象,晦涩难懂,不同的问题的求解思路也是千差万别,但是从本质上来看动态规划问题,最核心思想就是将一个大的问题拆分成一个一个的...
  • 巧妙理解动态规划算法

    千次阅读 2020-04-10 12:01:17
    我们先来看一个题目:有一座高度是10级台阶的楼梯,从下往上走,每跨一步...那到底什么是动态规划呢? 动态规划的英文名是Dynamic Programming,是一种分阶段求解决策问题的数学思想。它不仅用于编程领域,也应用于管

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,490
精华内容 11,796
关键字:

动态规划的核心思想是什么