精华内容
下载资源
问答
  • 动态规划-重叠子问题

    2017-06-20 18:30:00
    动态规划-重叠子问题 flyfish 2015-8-23 名词解释 重叠子问题 overlapping subproblems 动态规划策略将问题分解为一个或者多个子问题 重叠子问题是一个递归解决方式里包括的子问题尽管非常多,但不同子问题...

    动态规划-重叠子问题

    flyfish 2015-8-23

    名词解释
    重叠子问题 overlapping subproblems

    动态规划策略将问题分解为一个或者多个子问题

    重叠子问题是一个递归解决方式里包括的子问题尽管非常多,但不同子问题非常少。少量的子问题被重复解决非常多次。

    比如LCS(最长公共子序列)问题,给定两个序列X和Y,长度各自是m和n,穷举子问题是指数级的,而不同子问题的数量仅仅是mn.

    a recurisive algorithn for the problem solves the same subproblems over and over,rather than always generating new subproblems.
    用来解原问题的递归算法能够重复地解相同的子问题。而不是总在产生新的子问题。

    over and over 重复。再三
    rather than 而不是。宁可…也不愿

    When a recursive algorithm revisits the same problems repeatedly,we say that the optimization problem has overlapping subproblems.
    当一个递归算法不断地调用同一问题时,我们说该最优问题包括重叠子问题

    revisit 英 [riː’vɪzɪt] 美 [ri’vɪzɪt]
    vt. 重游;再訪;重临
    n. 再訪问

    repeatedly 英 [rɪ’piːtɪdlɪ] 美 [rɪ’pitɪdli]
    adv. 重复地;再三地。屡次地

    In contrast, a problem for which a divide-and-conquer approach is suitalbe usually generates brand-new problems at each step of the recursion.
    相反地,适用于分治法解决这个问题往往在递归的每一个步上都产生全新的问题。

    contrast英 [‘kɒntrɑːst] 美 [‘kɑntræst]
    vi. 对照;形成对照
    vt. 使对照;使与…对照
    n. 对照;区别。对照物

    divide-and-conquer
    分治法

    approach 英 [ə’prəʊtʃ] 美 [ə’protʃ]
    n. 方法;途径;接近
    vt. 接近;着手处理
    vi. 靠近

    suitable 英 [‘suːtəb(ə)l] 美 [‘sutəbl]
    adj. 适当的。相配的

    brand-new
    adj. 崭新的;近期获得的

    brand 英 [brænd] 美 [brænd]
    vt. 铭刻于,铭记;打烙印于;印…商标于
    n. 商标,牌子;烙印

    以斐波那契数列为例说明

    斐波那契数列指的是这样一个数列:1、1、2、3、5、8、13
    从第3个数開始。每一个数都是前面两个数之和。
    測试时 输入的 n>=3,但也不要太大,防止溢出。
    递归式

    Consider again the recursive function for computing the nth Fibonacii number
    .
    再次考虑使用递归函数计算第n个斐波那契数。

        int Fibonacci(int n)
        {
            if( (1==n) || (2==n) )
            return 1;
    
            return Fibonacci(n-1) + Fibonacci(n-2);     
        }
    
    调用 Fibonacci(7)。

    存表方式
    动态规划算法总是充分利用重叠子问题。即通过每一个子问题仅仅解一次,把解保存在一个须要时就能够查看的表中,而每次查表的时间为常数。


    Dynamic-programming algorithms typically take advantage of overlapping subproblems by solving each subproblem once and then storing the solution in a table where it can be looked up when needed, using constant time per lookup.

    typically 英 [‘tɪpɪkəlɪ] 美 [‘tɪpɪkli]
    adv. 代表性地;作为特色地,典型地

    take advantage of
    利用

        int Fibonacci(int n,int* Values)
        {
            if(n<=2)
            return 1;
    
            Values[n]=Fibonacci(n-1,Values) + Fibonacci(n-2,Values);
    
            return  Values[n];  
        }
    
    调用
    int Values[8]={0,0,0,0,0,0,0,0};
    Fibonacci(7,Values); 

    不须要表存储全部值。仅仅存储前两个值

    int Fibonacci(int n)
        {
            long past,prev,curr;
            past=prev=curr=1;
    
            for(int i=3;i<=n;i++)
            {
                past=prev;      // past holds Fibonacci(i-2)
                prev=curr;      // past holds Fibonacci(i-1)
                curr=past+prev; // current now Fibonacciholds (i)
            }
            return curr;
    
        }
    
    
    调用 Fibonacci(7)。
    展开全文
  • 问题存在”重叠子问题“   暴力穷举效率低下,需要通过”备忘录“或者”DP table“优化穷举。 问题具备”最优子结构“   通过子问题最值得到原问题最值 问题的”状态转移方程“   第一:问题最简单的情况是...

    动态规划(Dynamic Programming)

      运筹学的一种最优化方法,常用于计算机应用,如求最长递增子序列,最小编辑距离。

    1. 问题形式

    求最值

    核心方法: 穷举

    • 列出所有可行解
    • 找最值

    2. 问题特点

    状态、选择、dp数组定义

    • 问题存在”重叠子问题“
        暴力穷举效率低下,需要通过”备忘录“或者”DP table“优化穷举。
    • 问题具备”最优子结构“
        通过子问题最值得到原问题最值
    • 问题的”状态转移方程“
        第一:问题最简单的情况是什么?
        第二:问题有哪些”状态“?
        第三:对于每个”状态“,有哪些”选择“使得
           ”状态“发生改变?
        第四:如何定义dp数组/函数来表现”状态“和”选择“?

    3. 案例

    3.1重叠子问题(斐波那契数列)

    在这里插入图片描述
    3.1.1 暴力递归(提出问题)
    斐波那契数列数学形式:递归
    代码:

    int fib(int N){
    	if(N==0){
    		return 0;
    	}	
    	if(N==1||N==2){
    	    return 1;
    	}
    	return fib(N-1)+fib(N-2);
    }
    

    上述代码:
    优点:简单易懂
    缺点:低效
    分析:假设n=20时,它的递归树为:
    在这里插入图片描述求原问题fib(20)值:
      (1)先计算子问题fib(19)和fib(18)
      (2)然后计算fib(19)
         需计算fib(18)和fib(17)
         …
         以此类推
         计算fib(1)和fib(2)
      (3)返回结果,递归树不向下生长。
    递归算法时间复杂度计算:

    子问题个数 * 一个子问题需要的时间

    • 子问题个数=递归树中节点的总数
        因为二叉树节点总数为指数级别,所以子问题个数的时间复杂度为O(2n)。
    • 一个子问题需要的时间
        因为无循环,只有fib(n-1)和fib(n-2)的加法操作,所以时间复杂度为O(1)。

    综上:时间复杂度O(2n)(即两者之积)

       通过观察递归树,算法低效的原因:大量重复计算。如fib(18)被计算两次。fib(18)为根的递归树体量巨大,多算一遍消耗大量时间,同时不止fib(18)这一个节点被重复计算。

    上述重复计算的过程被称为重叠子问题

    3.1.2 带备忘录的递归解法(解决问题)
      通过分析上述提出的重叠子问题,知道造成耗时的原因是重复计算,那么我们可以造一个”备忘录“,每次算出某个子问题的答案后先不要返回,而是先将其记到”备忘录“里再返回;每次遇到一个子问题先去”备忘录“里查一查,如果发现之前解决过这个问题,可以直接引用这个答案,不需要重复计算了。
      ”备忘录“:数组或者哈希表(字典)
    代码:

    		int fib(int N){
    			if(N==0){
    				return 0;
    			}
    			//将备忘录全部初始化为0
    			vector<int>memo(N+1,0);
    			//进行备忘录的递归
    			return helper(memo,N);
    		}
    
    
    		int helper(vector<int>&memo,int n){
    			//base case最简单的情况
    			if(n==1||n==2){
    				return 1;
    			}
    			//已经计算过的情况
    			if(memo[n]!=0){
    				return memo[n];
    			}
    			memo[n]=helper(memo,n-1)+helper(memo,n-2);
    			return memo[n];
    		}
    

    分析:假设n=20时,“备忘录”的递归树:
    在这里插入图片描述通过“备忘录”上述递归树进行了”剪枝“,改造成了一幅不存在冗余的递归图(其中为了方便书写fib()函数写成f()函数):
    在这里插入图片描述递归算法时间复杂度计算:

    • 子问题个数=图中节点的总数
        因为不存在冗余计算,子问题就是f(1)、f(2)、f(3)…f(20),数量和输入规模N=20成正比,所以子问题个数为O(N)。
    • 一个子问题需要的时间
        因为无循环,只有f(n-1)和f(n-2)的加法操作,所以时间复杂度为O(1)。

    综上:时间复杂度O(N)(即两者之积)

       与暴力算法相比,效率提高了许多

    总结1:

       带“备忘录”的递归解法的效率已经和迭代的动态规划解法一样了。实际上,这种解法和迭代的动态规划已经差不多了。
       带备忘录的递归解法解法:“自顶向下”
       动态规划:“自底向上”的。

    啥叫“自顶向下”?

       我们刚才画的递归树(或者说图),是从上向下延伸的,都是从一个规模较大的原问题,比如f(20),向下逐渐分解规模,直到f(1)和f(2)这两个base case, 然后逐层返回答案, 这就叫“自顶向下”。

    啥叫“自底向上”?

       与上述相反,我们直接从最下面、最简单、问题规模最小的f(1)和f(2)开始往上推,直到推到我们想要的答案f(20),这就是动态规划的思路,这也是为什么动态规划一般都脱离了递归,而是由循环迭代完成计算的关键所在。

    3.1.3 dp数组的迭代解法(解决问题)
       有了上一步“备忘录”的启发,我们可以把这个“备忘录”独立出来成为一张表,就叫作DP table, 在这张表上完成“自底向上”的推算!

    		int fib(int N){
    			if(N==0){
    				return 0;
    			}
    			if(N==1||N==2){
    				return 1;
    			}
    			vector<int>dp(N+1,0);
    			//base case
    			dp[1]=dp[2]=1;  
    			for(int i=3;i<=N;i++){
    				dp[i]=dp[i-1]+dp[i-2];
    			}
    			return dp[N];
    		}
    

    DP table表如下:
    在这里插入图片描述  DP table特别像之前那个“剪枝”后的结果,只不过反过来了。实际上带备忘录的递归解法中的”备忘录“最终就是这个DP table, 所以说这两种解法其实是差不多的, 在大部分情况下, 效率也基本相同。
      这里引出了“状态转移方程”这个名词,实际上就是描述问题结构的数学形式:
    在这里插入图片描述

    为哈叫“状态转移方程”?

      把f(n)想作一个状态n,这个状态n是由状态n-1和状态n-2相加转移而来,这就叫状态转移。

    总结2:

      上面的几种解法中的所有操作, 例如语句return f(n-1) +f(n-2) ,dp[i] =dp[i 1-1] +dp[i-2], 以及对“备忘录”或DP table的初始化操作, 都是围绕这个方程式的不同表现形式,由此可见列出“状态转移方程”的重要性,它是解决问题的核心。而且很容易发现,其实状态转移方程直接代表着暴力解法。
      动态规划问题最困难的就是写出暴力解法,即状态转移方程。只要写出暴力解法, 优化方法无非是用“备忘录"或者DP table。
      在这个例子的最后,有一个细节的优化。根据斐波那契数列的状态转移方程, 当前状态只和之前的两个状态有关, 其实并不需要那么长的一个DP table来存储所有的状态,只要想办法存储之前的两个状态就行了。所以,可以进一步优化,把空间复杂度降为O(1);

    		int fib(int N){
    			if(N==0){
    				return 0;
    			}
    			if(N==1||N==2){
    				return 1;
    			}
    			int pre=1,curr=1;  
    			for(int i=3;i<=N;i++){
    				int sum=pre+curr;
    				pre=curr;
    				curr=sum;
    			}
    			return curr;
    		}
    

      这个技巧就是所谓的“状态压缩”, 如果我们发现每次状态转移只需要DP table中的一部分, 那么可以尝试用状态压缩来缩小DP table的大小, 只记录必要的数据, 上述例子就相当于把DP table的大小从N缩小到2。 一般来说是把一个二维的DP table压缩成一维, 即把空间复杂度从O(N2) 压缩到O(N)。
      关于涉及动态规划的另一个重要特性“最优子结构”?下面会涉及。斐波那契数列的例子严格来说不算动态规划,因为没有涉及求最值,以上旨在说明重叠子问题的消除方法,演示为得到最优解法而逐步求精的过程。

    展开全文
  • 动态规划(篇1)重叠子问题

    千次阅读 2017-03-14 09:23:55
    在这篇文章中,我们将详细讨论第一个属性(重叠子问题)。动态规划的第二个属性在下一篇文章即动态规划篇2中讨论。1)重叠子问题 2)最佳子结构 1)最佳子结构 像分治法一样,动态规划包含了对子问题的解决。动态...

    动态规划是一种算法范例,通过将其分解为子问题来解决给定的复杂问题,并存储子问题的结果,以避免再次计算相同的结果。 以下是一个问题的两个主要属性,表明给定的问题可以使用动态规划来解决。
    在这篇文章中,我们将详细讨论第一个属性(重叠子问题)。

    1)重叠子问题
    2)最佳子结构
    1)重叠子问题:
    像分治法一样,动态规划包含了对子问题的解决。动态规划主要用于不断地解决相同子问题。在动态规划中,子问题的计算解被存储在表中,使得这些不必重新计算。因此,当没有公共(重叠)子问题时,就不会使用动态规划。例如,二分搜索没有公共子问题。如果我们以斐波纳契数字的递归程序为例,有很多子问题会被反复解决。

    /* simple recursive program for Fibonacci numbers */
    int fib(int n)
    {
       if ( n <= 1 )
          return n;
       return fib(n-1) + fib(n-2);
    }

    fib(5)的递归树如下:

    
                              fib(5)
                         /             \
                    fib(4)               fib(3)
                 /      \                /     \
             fib(3)      fib(2)         fib(2)    fib(1)
            /     \        /    \       /    \
      fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
      /    \
    fib(1) fib(0)

    我们可以看到函数f(3)被调用了2次。如果我们将存储f(3)的值,则不再计算它,我们可以重用旧的存储值。有以下两种不同的方法来存储值,以便可以重用这些值:
    a)记忆(自上而下)
    b)制表(自下而上)
    a)记忆(自上而下):用于问题的记忆程序类似于具有小修改的递归版本,它在计算解之前查找查找表。我们初始化一个所有初始值为NIL的查找数组。每当我们需要解决子问题时,我们首先查找查找表。如果预先计算的值存在,那么我们返回该值,否则我们计算值,并将结果放在查找表中,以便以后可以重复使用。

    以下是第n斐波纳契数字的记忆版本。

    /* C/C++ program for Memoized version for nth Fibonacci number */
    #include<stdio.h>
    #define NIL -1
    #define MAX 100
    
    int lookup[MAX];
    
    /* Function to initialize NIL values in lookup table */
    void _initialize()
    {
      int i;
      for (i = 0; i < MAX; i++)
        lookup[i] = NIL;
    }
    
    /* function for nth Fibonacci number */
    int fib(int n)
    {
       if (lookup[n] == NIL)
       {
          if (n <= 1)
             lookup[n] = n;
          else
             lookup[n] = fib(n-1) + fib(n-2);
       }
    
       return lookup[n];
    }
    
    int main ()
    {
      int n = 40;
      _initialize();
      printf("Fibonacci number is %d ", fib(n));
      return 0;
    }

    b)制表(自下而上):给定问题的制表程序以自下而上的方式构建表,并返回表中的最后一个条目。例如,对于相同的斐波纳契数,我们首先计算fib(0),fib(1),fib(2),fib(3)等等。因此,从字面上看,我们正在建立自下而上的子问题的解决方案。

    以下是第n个斐波纳契数字的表格版本。

    /* C program for Tabulated version */
    #include<stdio.h>
    int fib(int n)
    {
      int f[n+1];
      int i;
      f[0] = 0;   f[1] = 1; 
      for (i = 2; i <= n; i++)
          f[i] = f[i-1] + f[i-2];
    
      return f[n];
    }
    
    int main ()
    {
      int n = 9;
      printf("Fibonacci number is %d ", fib(n));
      return 0;
    }

    输出:

     斐波纳契数为34
    展开全文
  • 目录什么是动态规划动态规划的递归写法——重叠子问题动态规划的递推写法——最优子结构总结结论分治与动态规划——重叠子问题贪心与动态规划——最优子结构参考文档 什么是动态规划 动态规划(Dynamic Progr...

    入门动态规划之前需要明确:

    1. 动态规划没有固定写法,极其灵活,常常需要具体问题具体分析
    2. 多训练、多思考、多总结是学习动态规划的重点;
    3. 《算法笔记》上大多是使用递推来实现动态规划的,很少用递归,感觉是因为递推比递归好理解一些,可以先学会递推再写递归
    4. 但是 需要明确很多的动态规划的题目都会结合DFS(即深度优先搜索)考察,所以递归还是非常有必要的!

    今天也是为了cc,努力奋斗的一天ヾ(≧▽≦*)o

    1. 什么是动态规划

    动态规划(Dynamic Programming,DP) 是一种用来解决一类 最优化问题 的算法思想。

    简单来说:

    1. 最优子结构:动态规划将一个复杂的问题分解成若干个子问题,通过综合子问题的最优解来得到原问题的最优解。(“”与“”体现在 状态转移方程

      其实有时候用动态规划也不一定就是最优解那种意思。
      比如斐波拉契数列,我们很难从中体会到最优解的意味。
      我感觉这句话是在告诉我们:出现最优解的问题的时候,要第一时间想到动态规划,不是最优解的问题时,也要想到动态规划分解子问题的思想!

    2. 重叠子问题:动态规划会将每个求解过的子问题的解记录下来,这样当下一次碰到同样的子问题时,就可以直接使用之前记录的结果,而不是重复计算。(虽然动态规划使用这种方式来提高计算效率,但不能说这种做法就是动态规划的核心)

      所谓 记录就是dp数组

    动态规划的写法:

    • 递归
    • 递推

    其中递归写法在此处又称作 记忆化搜索记忆化搜索在机试中出现频率不要太高!

    附:

    因为状态转移方程体现了动态规划重叠子问题和最优子结构这两个特性,因此书写状态转移方程是最困难的。下面是从网上学到的一个思维框架,用于辅助思考状态转移方程:

    明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

    按上面的套路走,最后的结果就可以套这个框架:

    # 初始化 base case
    dp[0][0][...] = base
    # 进行状态转移
    for 状态1 in 状态1的所有取值:
        for 状态2 in 状态2的所有取值:
            for ...
                dp[状态1][状态2][...] = 求最值(选择1,选择2...)
    

    2. 动态规划的递归写法——重叠子问题

    这一部分重点需要理解的是动态规划是如何 记录子问题的解,来避免下次遇到相同的子问题时的重复计算

    下面是一个不记录重复解的例子,复杂度为O(2n)O(2^n),爆炸~~~ :
    在这里插入图片描述
    为了避免重复计算,可以开一个一维数组dp,用来保存已经计算过的结果,其中dp[n]记录F(n)的结果,并用dp[n]=-1表示F(n)当前还没有被计算过。

    int dp[MAXN];
    

    然后就可以在递归当中判断dp[n]是否等于-1:如果不是-1,说明已经计算过F(n),直接返回dp[n]就是结果;否则,按照递归式进行递归。代码如下:

    int F(int n){
    	if(n == 0||n == 1) return 1;	//递归边界
    	if(dp[n] != -1) return dp[n];
    	else{
    		dp[n] = F(n-1) + F(n-2);
    		return dp[n];
    	}
    }
    

    通过上述的 记忆化搜索(即记忆化搜索等于DFS+dp数组),将复杂度从 O(2n)O(2^n)降为O(n)O(n)

    上面的例子还引申了一个概念:如果一个问题可以被分解成若干个子问题,且这些子问题会重复出现,那么称这个问题拥有 重叠子问题(Overlapping Subproblems)

    一个问题必须拥有重叠子问题,才能使用动态规划去解决。

    3. 动态规划的递推写法——最优子结构

    最优子结构——数塔问题

    下面以数塔问题为例:

    在这里插入图片描述
    在这里插入图片描述
    出于上面的考虑,不妨令dp[i][j]表示从第i行第j个数字出发的到达最底层的所有路径中能得到的最大和。在定义这个数组之后,dp[1][1]就是最终想要的答案~
    需要注意到的是:如果要求出“从位置(1,1)到达最底层的最大和”dp[1][1],那么一定要先求它的两个子问题“从位置(2,1)到达最底层的最大和”dp[2][1]和“从位置(2,2)到达最底层的最大和”dp[2][2],即进行一次决策:从数字5的左下还是右下。于是有:

    dp[1][1] = max(dp[2][1],dp[2][2])+f[1][1]
    

    抽象出来是:

    dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j]
    

    dp[i][j]称为问题的状态,而把上面的式子称作状态转移方程,它把状态dp[i][j]转移为dp[i+1][j]dp[i+1][j+1]
    可以发现第i层的状态只与第i+1层的状态有关。

    • 那么,如果将层号增大,什么时候会到头呢?
      可以发现,数塔的最后一层的dp值总是等于元素本身,即dp[n][j] = f[n][j](1<=j<=n),把这种直接确定其结果的部分称为边界,而 动态规划的递推写法总是从这些边界出发,通过状态转移方程扩散到整个dp数组。
      代码:
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    const int maxn = 1000;
    
    int f[maxn][maxn],dp[maxn][maxn];
    
    int main(){
    	int n;
    	scanf("%d",&n);
    	for(int i = 1;i <= n;++i){
    		for(int j = 1;j <= i;j++){
    			scanf("%d",&f[i][j]);	//输入数塔 
    		}
    	}
    	
    	//边界
    	for(int j=1;j<=n;++j){
    		dp[n][j] = f[n][j];
    	}
    	
    	//从第n-1层不断往上计算出dp[i][j]
    	for(int i = n-1;i>=1;i--){
    		for(int j=1;j<=i;++j){
    			//状态转移方程
    			dp[i][j] = max(dp[i+1][j],dp[i+1][j+1]) + f[i][j]; 
    		}
    	}
    	printf("%d\n",dp[1][1]);	//dp[1][1]即为需要的答案 
    	return 0;
    }
    
    

    显然,使用递归也可以实现上面的例子。递归与递推的区别在于:

    • 递推写法自底向上(Bottom-up Approach),即从边界开始,不断向上解决问题,直到解决了目标问题;
    • 递归写法自顶向下(Top-down Approach),即从目标问题开始,将它分解成子问题的组合,直到分解至边界为至。

    通过上面的例子再引申一个概念:

    如果一个问题的最优解可以由其子问题的最优解有效地构造出来,那么称这个问题拥有 最优子结构(Optimal Substructure)。最优子结构保证了动态规划中原问题的最优解可以由子问题的最优解推导而来。

    最优子结构——凑零钱

    在这里插入图片描述
    一个问题必须拥有最优子结构,才能使用动态规划去解决。

    要符合最优子结构,子问题间必须相互独立。啥叫相互独立?你肯定不想看数学证明,我用一个直观的例子来讲解。

    比如说,你的原问题是考出最高的总成绩,那么你的子问题就是要把语文考到最高,数学考到最高…… 为了每门课考到最高,你要把每门课相应的选择题分数拿到最高,填空题分数拿到最高…… 当然,最终就是你每门课都是满分,这就是最高的总成绩。

    得到了正确的结果:最高的总成绩就是总分。因为这个过程符合最优子结构,“每门科目考到最高”这些子问题是互相独立,互不干扰的。

    但是,如果加一个条件:你的语文成绩和数学成绩会互相制约,此消彼长。这样的话,显然你能考到的最高总成绩就达不到总分了,按刚才那个思路就会得到错误的结果。因为子问题并不独立,语文数学成绩无法同时最优,所以最优子结构被破坏。

    那么,既然知道了这是个动态规划问题,就要思考如何列出正确的状态转移方程

    先确定状态,也就是原问题和子问题中变化的变量。由于硬币数量无限,所以唯一的状态就是目标金额 amount

    然后确定 dp 函数的定义:当前的目标金额是 n,至少需要 dp(n) 个硬币凑出该金额。

    然后确定「选择」并择优,也就是对于每个状态,可以做出什么选择改变当前状态。具体到这个问题,无论当的目标金额是多少,选择就是从面额列表 coins 中选择一个硬币,然后目标金额就会减少。

    最后明确 base case,显然目标金额为 0 时,所需硬币数量为 0;当目标金额小于 0 时,无解,返回 -1。

    4. 总结

    (1) 结论

    一个问题必须拥有重叠子问题和最优子结构,才能使用动态规划去解决。

    下面指出这两个概念的区别:

    (2) 分治与动态规划——重叠子问题

    • 相同点:
      将问题分解成子问题,然后合并子问题的解得到原问题的解。

    • 不同点:
      分治法解决的问题不拥有重叠子问题,解决的问题不一定是最优化问题;
      动态规划解决的问题拥有重叠子问题,解决的问题一定是最优化问题。

    • 例子:
      分治法:快速排序、归并排序等。

    (2) 贪心与动态规划——最优子结构

    • 相同点
      都要求原问题必须拥有最优子结构

    • 不同点
      贪心的计算方式类似于”自顶向下“,但是并不等待所有子问题求解完毕后再选择使用哪一个,而是通过一种策略直接选择一个子问题去求解,没被选择的子问题就不会再去求解了。
      动态规划的计算方式有”自顶向下“和”自底向上“两种,都是从边界开始向上得到目标问题的解。也就是说,它总是会考虑所有子问题,并选择继承能得到最优结果的那个,对暂时没有被继承的子问题,由于重叠子问题的存在,后期可能会再次考虑它们,因此还有机会成为全局最优的一部分,不需要放弃。

    5. 题型训练

    1. LeetCode 62. Unique Paths
    2. LeetCode 63. Unique Paths II
    3. LeetCode 64. Minimum Path Sum

    6. 参考文档

    算法笔记

    展开全文
  • 动态规划研究的问题 内容 ...动态规划子问题重叠性质 前向优化 后向优化 例 5.1.2 连续变量的资源分配问题 例 5.3.2 多阶段有限资源分配问题 递推方程 例 5.3.1 解TSP问题 计算一个单元格 计算过程
  • 当遇到一个问题,想要使用动态规划的基础是发现重叠子问题 以LeetCode 343 整数拆分 这道题为例 题目 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 ...
  • 动态规划(1)-重叠子问题的性质

    千次阅读 2014-03-10 10:53:07
    1)重叠子问题2)最优子结构 1)重叠子问题: 像分而治之,动态规划也把问题分解为子问题。动态规划主要用于:当相同的子问题的解决方案被重复利用。在动态规划中,子问题解决方案被存储在一个表中,以便这些不必...
  • 动态规划,将递归转换为自底向上的方式计算,注意数组要初始化为0 279完全平方数 class Solution { int mem[20000]={}; public: int numSquares(int n) { if(mem[n]>0) return mem[n]; for(int i=1;i(int)sqrt(n);i...
  • 文章目录1 概念2 递归写法3 递推写法4 总结4.1 区别4.2 应用条件4.2.1 最优子结构4.2.2 重叠子问题4.2.3 条件4.2.4 区别4.2.4.1 分治和动态规划4.2.4.2 贪心和动态规划 1 概念 动态规划(Dynamic Programming,DP)...
  • 记录重叠子问题的解 以计算Fibonacci数列为例,最简单粗暴的算法是 int F(int n) { if(n == 0 || n == 1) return 1; else return F(n - 1) + F(n - 2); } 例如计算F(5)时,如图,有大量重复计算,造成效率低下...
  • 所以动态规划在非一般(重叠子问题的情况下不是那么有用,因为找不到啥存储结果的提升当这个结果不再需要了,例如,二分查询就不具有一般子问题。如果我们用斐波那契数最为递归编程的例子,那么就有许多的问题需要...
  • 最优化问题,即要做出一组...与分治法不同的是,动态规划面对的子问题并不是相互独立的,各子问题有可能包含公共的子子问题。 1)描述最优解的结构 2)递归定义最优解的值 3)按自底向上的方式计算最优解的值。 4)由计
  • 动态规划(dynamic programming)简称DP。 先看3个简单的问题: 1,斐波那契数列 1,1,2,3,5,8...... 求第n项 int fac(int n) { if(n<3)return 1; return fac(n-1)+fac(n-2); } 时间复杂度O (1.6 ^ n) ...
  • 1) + fib(n -2) def fastfib(n, memo): global numbcalls numbcalls += 1 if n not in memo: # 减少了重叠部分的计算 memo[n] = fastfib(n-1, memo) + fastfib(n-2, memo) return memo[n] def fib1(n): memo = {0:1,...
  • 那么我们就要清楚动态规划方法的最优化问题中的两个要素:最优子结构和重叠子问题。  1、最优子结构  1)如果问题的一个最优解包含了子问题的最优解,则该问题具有最优子结构。当一个问题具有最优子结构的时候,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,821
精华内容 728
关键字:

动态规划重叠子问题