精华内容
下载资源
问答
  • 重叠子问题

    千次阅读 2014-04-19 20:32:23
    做了几道题让我想起一个问题,就是

    做了几道题让我想起一个问题,就是重叠子问题这个思想。

    记得动态规划优化问题的两个要素就是,最优子结构和重叠子问题。

    关于重叠子问题的优化,就是这些子问题可能多次用到,多次计算,所以可以事先计算了,然后用到的时候查表。

    比如之前的codejam的B题,里面就有重叠子问题,小数据的时候,一般都可以写出,而大数据的时候你再用一般的方法,程序跑出结果的时间就非常慢,而如果事先预处理,将一定范围的值先计算出来,需要的时候查表即可,速度快了很多。

    再如UVa 253题,你可以根据每次输入进行立方体的旋转变化,但如果你事先将24种状态都计算出来,后面只需要对24种状态查找即可。

    我们常常考虑问题都是对一组数据来看,所以往往最初设计或实现的算法都是针对一组数据,稍加注意,就可以用重叠子问题来优化。有时候也能想到计算出一个大范围内的数据,但总会觉得计算得多了(比如,对于n=5,你只需要计算到5就行了,而你用打表的方法,可能是事先计算到n=10000;对于n=5这组数据来说,这样的确是计算得太多了,但从整体输入来说,省去了很多重复的计算)这样的方法,单从一组数据来看,肯定是直接计算该组数据来得快些,但从大规模输入数据,比如ACM题的大量输入来看,则优化了很多。有的直接是从O(n2)的复杂度降到了O(n);直观的对比,就是codejam的B题,用两种方法,效率差别太大。

    之前自己已经有这个思想了,太久没做题,好像忘了,刚刚做UVa 253 自己突然想到了。借此提醒一下自己。

    展开全文
  • 你真的了解动态规划中的重叠子问题吗?! 他真的是你想的那样的吗?!

    如果你对其他算法知识感兴趣的话,可以考虑阅读我的专栏:

    算法设计与分析【专栏】

    重叠子问题

    事情经过

      今天,我在做动态规划算法相关实验的时候,考虑到了动态规划的两大特性: 最优子结构和重叠子问题。

      最优子结构的话,没什么好说的,就是原问题的最优解包含子问题的最优解。如果大家不理解的话,我就粗略的介绍一下我的理解:一个国家中有一名最强力的士兵(也就是问题的最优解),那么他必须是他所在军营中最强力的士兵(也是子问题的最优解),这样他才可能是这个国家最强力的士兵。

      其中重叠子问题引起了我的注意,以前我对于这个概念就是一知半解的,经过我在网上粗略的查询了一下,网上大部分人对这个概念的理解为:子问题之间计算重复太多次,可以通过填表来解决这个问题。

      此时我就纳闷了,这么说的话,那么动态规划就还应该有一个特性啊,也就是子问题之间不独立(这个是区分分治算法的关键,我认为很重要)。

      于是我便去粗略的查找了书籍,发现书上并没有对此的专门解释(也有可能有,我没找到),于是我便自己总结了一下:

    重复子问题:子问题的计算出现重复,填表解决。
    重叠子问题:子问题之间不独立。

      然后就是沉醉在:我好厉害啊!我都会自己定义名词了!以后就叫小王定理吧!

      抽完风之后,我便开始在网上认真寻找重叠子问题的概念了,皇天不负有心人,终于让我在有道上找到了专门的解释(也就是下图)。
    在这里插入图片描述
      那这么说的话,动态规划的特性就可以总结为:最优子结构性质和重叠子问题。(小王定理没了!)

      虽然结果和我当初想的不太一样,但这次经历还是让我欣喜半天(尤其是我自己定义名词的时候),我也对这个名词有了更加深刻的印象,也希望大多数人也不要想我当初一样,在理解的时候被误导了。

      这时我又产生了新的疑问,导致重复计算的原因会不会是子问题之间的不独立呢(我脑溢血想出来的)?希望大家可以发表一下自己的观点,以上都是本人的粗略看法,希望大神勿喷。

    后话

    1. 首先给大家说一下,博主经常在线,如果有什么问题或者想法,可以在下方评论,我会积极反馈的。
    2. 其次还是要请大家能够多多指出问题,我也会在评论区等候大家!
      在这里插入图片描述 .
      还有就是不够2000字不能参加原力计划,好烦!
    展开全文
  • 动态规划-重叠子问题

    千次阅读 2015-08-23 19:06:51
    动态规划-重叠子问题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);
    展开全文
  • 在讲动态规划课时,我们知道可用动态规划算法求解的问题应具备的一个基本要素是子问题的重叠性质,矩阵连乘问题能用动态规划求解正是因为它具有重叠子问题。因此在解矩阵连乘问题的自顶向下的递归算法中,存在着大量...
  • 主要介绍了用Python展示动态规则法用以解决重叠子问题的一个棋盘游戏的示例,动态规划常常适用于有重叠子问题和最优子结构性质的问题,且耗时间往往远少于朴素解法,需要的朋友可以参考下
  • 动态规划(篇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
    展开全文
  • 文章目录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)...
  • 动态规划(1)-重叠子问题的性质

    千次阅读 2014-03-10 10:53:07
    1)重叠子问题2)最优子结构 1)重叠子问题: 像分而治之,动态规划也把问题分解为子问题。动态规划主要用于:当相同的子问题的解决方案被重复利用。在动态规划中,子问题解决方案被存储在一个表中,以便这些不必...
  • 目录什么是动态规划动态规划的递归写法——重叠子问题动态规划的递推写法——最优子结构总结结论分治与动态规划——重叠子问题贪心与动态规划——最优子结构参考文档 什么是动态规划 动态规划(Dynamic Progr...
  • 先看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) 递归写法(备忘录法): int ans[1000]={0}...
  • 所以动态规划在非一般(重叠子问题的情况下不是那么有用,因为找不到啥存储结果的提升当这个结果不再需要了,例如,二分查询就不具有一般子问题。如果我们用斐波那契数最为递归编程的例子,那么就有许多的问题需要...
  • ireport解决报表重叠问题

    千次阅读 2017-06-10 18:10:32
    当一个主报表里包含多个报表,报表内部高度不确定时,如果报表都放在detail里,往往会出现报表重叠问题。 解决办法:为每一个报表分别添加一个group,注意报表高度不要太高,容易出现后面大片空白。 ...
  • 重叠子空间分类聚类算法.pdf
  • 针对上述问题,提出一种稀疏条件下的重叠子空间聚类(OSCSC)算法。算法利用l1范数和Frobenius范数的混合范数表示方法建立子空间表示模型,并对l1范数正则项进行加权处理,提高不同子空间的稀疏性和同一子空间的稠密...
  • 具有重叠子阵列架构的天线权重优化。
  • 基于概率模型的重叠子空间聚类算法.pdf
  • 稀疏条件下的重叠子空间聚类算法.pdf
  • 当父元素当中有一个子元素的时候,元素设置margin-top或者margin-bottom的时候会不起作用,也就是父元素之间并没有产生间距,但是这个值作用到了父元素的身上。具体代码如下:&lt;!doctype html&gt; &...
  • 局部加权最小二乘回归的重叠子空间聚类算法.pdf
  • 一种可重叠子空间K-Means聚类算法.pdf
  • 689. 三个无重叠子数组的最大和 给定数组 nums 由正整数组成,找到三个互不重叠的子数组的最大和。 每个子数组的长度为k,我们要使这3*k个项的和最大化。 返回每个区间起始索引的列表(索引从 0 开始)。如果有多个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 107,123
精华内容 42,849
关键字:

重叠子问题