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

    千次阅读 2019-10-23 12:47:17
    1、自底向上:思想是逆向的,但也能正向解答。两者是相同的,只是求解顺序不一样。 2、状态转移方程:对于这个,我只能说,暴力怎么解,动态规划就怎么解。因为求解动态规划的顺序是先暴力递归——带备忘录的递归...

    动态规划又叫做填表法,就是说动态规划就是个填表游戏
    1、自底向上:思想是逆向的,但也能正向解答。两者是相同的,只是求解顺序不一样。
    2、状态转移方程:对于这个,我只能说,暴力怎么解,动态规划就怎么解。因为求解动态规划的顺序是先暴力递归——带备忘录的递归——动态规划。并且看博客多了的人会发现,其实递归的递归体就是动态规划的状态转移方程。不同的思考,得出的状态转移方程也不一样
    3、最优子问题:大问题分成小问题,小问题寻找最优解构成大问题的最优解。这一点不必太在意,因为求解的过程就是在求解小问题的最优解。
    最后学习动态规划,当靠理论是不行的,得结合实战,下列给出动态规划的例子(之后会陆陆续续的增加各种各样的例子供大家学习)
    1、最大连续子序列和
    2、数字三角型最小路径
    3、最长公共子序列
    4、最长递增序列
    5、01背包问题(不同定义的不同解法)

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

    千次阅读 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
    
    */
    
    展开全文
  • class Solution { public: int maxProfit(vector<int>& prices) { int dp0 = 0, dp1 = INT_MIN, temp; for (int price : prices) { temp = dp0;... dp0 = max(dp0, dp1 + price);... dp1 = max(dp1, temp - ...
  • 动态规划——基本思想

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

    动态规划——基本思想

    动态规划的特点

    • 把原始问题划分为一系列子问题
    • 求解每个子问题仅一次,并将其结果保存在一个表中,以后用到时到时直接存取,不重复计算,节省计算时间
    • 自底向上地计算

    使用范围

    • 一类优化问题:可分为多个相关子问题,子问题的解被重复使用

    使用动态规划的条件

    • 优化子结构
      • 当一个问题的优化解包含了子问题的优化解时,这个问题具有优化子结构。
      • 缩小子问题集合,只需那些优化问题中包含的子问题,降低实现复杂性。
      • 优化子结构使得我们能自下向上地完成求解过程
    • 重叠子问题
      • 在问题的求解过程中,很多子问题的解将被多次使用

    设计步骤

    • 分析优化解的结构
    • 递归地定义最优解的代价
    • 自底向上地计算优化解的代价保存之,并获取构造最优解的信息
    • 根据构造最优解的信息构造优化解

    优化子结构的分类

    • 编号动态规划:输入为x1,x2,,xn,子问题是x1,x2,,xi,子问题复杂性为O(n)(最大不下降子序列问题)
    • 划分动态规划:输入为x1,x2,,xn,子问题为xi,xi+1,,xj,子问题复杂性是O(n2)(矩阵链乘问题)
    • 数轴动态规划:输入为x1,x2,,xn和数字C,子问题为x1,x2,,xiK(KC),子问题复杂性O(nC)(0-1背包问题)
    • 前缀动态规划:输入为x1,x2,,xny1,y2,,ym,子问题为x1,x2,,xiy1,y2,,yj,子问题复杂性是O(mn)(最长公共子序列问题)
    • 树形动态规划:输入是树,其子问题为子树,子问题复杂性是子树的个数。(树中独立集合问题)
    展开全文
  • 动态规划的思想

    千次阅读 2011-10-24 15:52:14
    动态规划的思想  动态规划( dynamic programming )算法是解决多阶段决策过程最优化问题的一种常用方法,难度比较大,技巧性也很强。利用动态规划算法,可以优雅而高效地解决很多贪婪算法或分治算法不能解决的...

     动态规划的思想

         动态规划( dynamic programming )算法是解决多阶段决策过程最优化问题的一种常用方法,难度比较大,技巧性也很强。利用动态规划算法,可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。动态规划算法的基本思想是:将待求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它进行求解,并把答案保存起来,让以后再次遇到时直接引用答案,不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果,与贪婪算法不同的是,在贪婪算法中,每采用一次贪婪准则,便做出一个不可撤回的决策;而在动态规划算法中,还要考察每个最优决策序列中是否包含一个最优决策子序列,即问题是否具有最优子结构性质。

        动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质:最优子结构性质和子问题重叠性质。

    1 、最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。

    2 、子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简 单地查看一下结果,从而获得较高的解题效率。

    当我们已经确定待解决的问题需要用动态规划算法求解时,通常可以按照以下步骤设计动态规划算法:

    1 、分析问题的最优解,找出最优解的性质,并刻画其结构特征;

    2 、递归地定义最优值;

    3 、采用自底向上的方式计算问题的最优值;

    4 、根据计算最优值时得到的信息,构造最优解。

    1 ~ 3 步是动态规划算法解决问题的基本步骤,在只需要计算最优值的问题中,完成这三个基本步骤就可以了。如果问题需要构造最优解,还要执行第 4 步; 此时,在第 3 步通常需要记录更多的信息,以便在步骤 4 中,有足够的信息快速地构造出最优解。

     

         动态规划其实质上是通过开辟记录表,记录已求解过的结果,当再次需要求解的时候,可以直接到那个记录表中去查找,从而避免重复计算子问题来达到降低时间复杂度的效果。实际上是一个空间换时间的算法。动态规划,通常可以把指数级的复杂度降低到多项式级别。一般算法书都会讲能不能用动态规划来求解问题,通常是判断有没有最有解结构,通常是通过“剪切技术”来判断:即证明问题的一个最优解中,使用的子问题的解本身也必须是最优的。通常是假设一个子问题不是最优的,那么找到一个最优的子问题来替换这个子问题,那么产生的最优解将优于已找到的那个最优解,从而矛盾。
        其实用不用动态规划来求解问题,还有一个关键是有没有重复的子问题。这也是使用动态规划与贪心法的区别所在。贪心法求解的问题也满足最优解结构,只是它能够在每一步都能够“贪婪的”选出当前唯一的最优子问题,并且当前的选择,是不依赖以前的选择的,通过这种“贪婪的选择”选到最后时,就得到了全局的最优解了,不会产生重复的子问题。而动态规划,在一步选择的时候,是通过从以前求出的若干个与本步骤相关的子问题最优解中选择最好的那个,加上这一步的值,来构
    造这一步那个子问题的最优解,而如果以前求出的若干个子问题不保存下来,就需要重新求(通常是递归所致)。动态规划用武之地也无非是保存这些重复的子问题而避免重新求解而达到高效的目的。
          动态规划的难点在于写出递推式。动态规划的步骤其实是很固定的,而每一个问题的递推式如何下手得到会因不同的问题而不同,这是个最关键的问题,没有通用的方法。通常是根据题目的问题,最终要求的问题,都会有几个数,以两个数M,N为例,然后让求最优值。你就可以使用v[M][N]数组来保存最有解,然后把问题替换成i,j两个数的问题,试图通过v[i][j]与前面求出来的解建立递推关系。建立递推关系后,你可以简单的写出递归形式的程序,这个程序只需要加上一条if(v[i][j]已求出) return v[i][j];就轻松改称了动态规划,这就是lookup的形式。当然如果已经有了递推式,你也很容易写出从底向上推的迭代形式。
         一般的算法书讲的动态规划都是来求解最优解的问题,或许最初是用来求解规划问题的,而规划必然是最优解问题,其实大多数的问题只要存在重复的子问题都可以使用动态规划的思路,就看你的重复的子问题是不是多的值得使用空间来换时间这个思路了。 

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

    千次阅读 2019-01-11 16:25:59
    分治法 将一个规模为n的问题分解为K个规模较小的子问题,这些子问题互相独立且与原问题相同。递归的解决这些问题,然后将各个子问题的解合并... 动态规划的实质是分治思想和解决冗余,因此动态规划是一种将问题 ...
  • 动态规划思想以及常见应用

    千次阅读 2018-03-30 18:30:52
    动态规划的基本思想以及和贪婪算法、分治法的比较动态规划的基本思想:将复杂问题进行分解,通过求解小规模子问题反推出原问题的结果。动态规划适合求解多阶段决策问题的最优解(可以简单理解为有状态转换的阶段...
  • 文章目录1.序2.动态规划的基本概念[^1]3.动态规划算法的基本思想[^2]4....这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。...
  • 将cglib动态代理思想带入Android开发

    千次阅读 2017-05-08 23:34:35
    动态代理在Android实际开发中用的并不是很多,但在设计框架的时候...我们今天来看看这个代理究竟是什么样子,在Android开发中如何使用它,以及将cglib动态代理思想在Android中看看如何实现。项目地址:MethodIntercept
  • 动态规划思想分析——经典题目

    千次阅读 2016-09-11 14:56:33
    动态规划思想是算法设计中很重要的一个思想,所谓动态规划就是“边走边看”,前面的知道了,后面的根据前面的也就可以推出来了。和分治算法相似又不同,相同的是都需要去寻找最优子结构,重复子问题,边界条件。不同...
  • 应用动态规划思想解决实际问题

    千次阅读 2017-04-01 11:08:13
    应用动态规划的思想解决实际问题--“数字三角形”和“LCS”
  • 动态规划之一:基本思想

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

    千次阅读 2010-02-12 23:28:00
    Spring框架中的AOP思想 动态代理模式一 AOP(Aspect oriented programming) 面向方面编程OOP面向对象编程AOP和OOP虽然在字面上十分相似,但却是面向不同领域的两种设计思想.OOP是在面向过程的编程方法基础上进行的改进...
  • Java动态代理+注解体现Spring AOP思想

    千次阅读 2017-07-31 15:48:52
    在MVC的架构中,优秀的代码是Service业务层只做业务逻辑处理,如果要添加新功能(如日志,事务等),不应该污染业务层代码。 ...1. 什么是动态代理?查理论能查几页纸,这里简单总结一句话:调用Pr
  • 微分动态规划的基本思想

    千次阅读 2017-08-02 01:37:19
    吴恩达cs229第19课,微分动态规划这一部分,看了两遍才看明白。 赶紧记下来: 微分动态规划是基于LQR(线性二次型)的, 后者能够比较简洁地计算最优策略,但要基于一个前提,就是 t+1 时刻的状态,是 t 时刻的...
  • 五大算法思想 动态规划 矩阵连乘问题、走金字塔问题、最长公共子序列问题、最长递增子序列问题、0-1背包问题、完全背包问题

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 354,825
精华内容 141,930
关键字:

思想动态是什么