自底向上_自底向上分析法 - CSDN
精华内容
参与话题
  • 从子问题解决原问题, 无非是两种方法,自底向上(Bottom-Up)与顶向下(Top-Down),形式上前者对应iteration,利用循环将结果存在数组里,从数组起始位置向后计算;后者对应recursion,即利用函数调用自身实现。如果...

    从子问题解决原问题, 无非是两种方法,自底向上(Bottom-Up)与自顶向下(Top-Down),形式上前者对应iteration,利用循环将结果存在数组里,从数组起始位置向后计算;后者对应recursion,即利用函数调用自身实现。如果不存储上一个状态的解,则为递归,否则就是DP。举个斐波那契数列(0,1,1,2,3,5…)的例子:

    1) 自底向上

    int array[n] = {0};
    array[1] = 1;
    for (int i = 2; i < n; i++)
        array[i] = array[i-1] + array[i-2];

    这里,为了说明方法,采用数组存储结果,空间复杂度O(n)。事实上,额外空间可以进一步缩小到O(1):利用几个变量记录之前的状态即可。由于我们记录了子问题的解,故给出的方法就是DP。事实上,自底向上的方式往往都是通过动态编程实现

    2) 自顶向下

    int Fibonacci(int n)
    {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        return Fibonacci(n-1) + Fibonacci(n-2);
    }

    为计算Fibonacci的第n个元素,我们先自顶向下地计算子问题:第n-1个元素和第n-2个元素。由于没有存储子问题的运算结果,我们给出的方法是递归

    递归与动态规划的异同

    什么是动态规划

    展开全文
  • 自底向上顶向下

    千次阅读 2018-04-04 14:25:48
    (以上可构造一个DAG)自底向上就是已经知道了所有递归边界,把所有可能的状态都算出来。基本步骤是一个拓扑排序的过程,从所有递归边界出发,当一个状态被所有可能的下层状态更新后,就用这个状态去更新...

    动态规划的式子都是状态P由状态Q1、Q2、Q3……之中选择一个或几个计算出来的形式,但是如果一直是一些状态这样递归下去,最后会无限循环的,所以每个式子一直写下去最后都会得到一些状态P是常数(递归边界)的形式。(以上可构造一个DAG)

    自底向上就是已经知道了所有递归边界,把所有可能的状态都算出来。基本步骤是一个拓扑排序的过程,从所有递归边界出发,当一个状态被所有可能的下层状态更新后,就用这个状态去更新后面的状态。直到所求的状态被彻底更新完成为止。

    自顶向下就是不考虑整个图结构,直接从要求的状态开始展开式子,如果式子中的某个状态的值还不清楚,就递归的从这个状态展开。递归结束后式子中的状态都被对应的值替换了,所求状态自然也就清楚了。


    作者:Adder
    链接:https://www.zhihu.com/question/31555807/answer/52463111
    来源:知乎
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    展开全文
  • 何谓"顶向下",何谓"自底向上

    万次阅读 2017-03-05 23:41:31
    相信每一个coder都听说过“顶向下”以及“自底向上”这两个名词。 我也是很早就听说过这两个名词,感觉是”不明觉厉”。 有一天,我打电话给一个做C语言开发的朋友说,我说我一直在做Java,想学一点C,问他有...

    相信每一个coder都听说过“自顶向下”以及“自底向上”这两个名词。
    我也是很早就听说过这两个名词,感觉是”不明觉厉”。

    有一天,我打电话给一个做C语言开发的朋友说,我说我一直在做Java,想学一点C,问他有什么好的建议。
    他说,他也有类似的想法,他说他一直在做C,想有机会学一点Java.然后他补充一句:他这是自底向上的学习,而我这叫自顶向下的学习。
    我当时一愣,不愧是老司机:原来这两个词表达的是学习过程相关的意思。

    • 直到不久前,我才知道,所谓的”自顶向下”与”自底向上”,指的是程序构造的两种不同的方式。换个说法,也可以说是“由粗到细”及“由细到粗”。

    • 怎么理解呢?举个栗子:

      假设现在有一个需求是这样的:将C盘里面的视频文件全部拷贝到D:\video\目录下。

    那么,由粗到细(自顶向下)的构造程序的方式是:先从大的方向考虑,完成这个程序需要那些步骤,比如:
    - 先判断有没有C盘
    - 再判断C盘里面有没有视频文件
    - 判断有没有D盘
    - 判断D盘是否还有存储空间
    - 拷贝C盘的视频到D盘
    - 结束
    先不考虑每个方法的具体实现,而是考虑一下,需要那些步骤,等整体步骤把握好了之后,再考虑这些步骤具体该怎么实现。比如:如何判断有没有C盘,如何判断C盘里面有没有视频文件等。
    这样子,先搭建骨架,等骨架搭建好了之后,再去填充具体内容。这种方式,就被称为由粗到细或者说自顶向下的构造方式。

    而与之相反,我们也可以先实现细节:比如:如果进行文件拷贝,如何判断有没有视频文件 。等这些具体的细节完成之后,再去搭建骨架,然后完成整个程序。这种,先完成细节功能,再组装到整体骨架中的方式就是由细到粗或者说是自底向上的构造程序的方式

    • 并不讨论哪种方式更好。在实际开发过程中,往往两种方式都会被运用到。
    展开全文
  • 动态规划(自底向上)

    千次阅读 2018-06-02 22:39:03
    动态规划 - 求解二项式系数(顶向下,自底向上) ref from http://jarg.iteye.com/blog/859391 博客分类: 算法设计 PascalJ# 1. 动态规划 备忘录法 备忘录方法采用顶向下方式,为每个解过的子问题建立了...


    1. 动态规划 备忘录法

    备忘录方法采用自顶向下方式,为每个解过的子问题建立了备忘录以备需要时查看,避免了相同子问题的重复求解。

    说明: 在非边界条件下,每次求解子问题时,先查找备忘录.

    若子问题已经求解过了,直接取出子问题的解;若未求解过,则求解并保存到备忘录中.

    此处的备忘录就是一个存储数据的容器.

    Java代码 复制代码 收藏代码
    1. /*
    2. @author: jarg
    3. @TODO 动态规划 - 备忘录法 求解二项式系数
    4. */
    5. /* 求解二项式系数 */
    6. public staticint Binomial(int n,int m)
    7. {
    8. /* 边界条件 */
    9. if(n==m || m==0)
    10. {
    11. return 1;
    12. }
    13. int date = readDate(n,m);
    14. if(date>0)
    15. {
    16. /*
    17. 子问题已经计算过
    18. 读取保存在备忘录中的数据
    19. */
    20. return date;
    21. }
    22. else
    23. {
    24. /*
    25. 子问题未计算过
    26. 解出子问题,将数据保存在备忘录中
    27. */
    28. int result = Binomial(n-1,m) + Binomial(n-1,m-1);
    29. writeDate(n,m,result);
    30. return result;
    31. }
    32. }
    33. /* 从备忘录中读取数据 */
    34. public staticint readDate(int n,int m)
    35. {
    36. for(int i=0;i<demo.size();i++)
    37. {
    38. Map<String,Integer> date = new HashMap<String,Integer>();
    39. date = demo.get(i);
    40. if(date.get("" + n + m) !=null)
    41. {
    42. return date.get("" + n + m);
    43. }
    44. }
    45. return 0;
    46. }
    47. /* 向备忘录中写入数据 */
    48. public staticvoid writeDate(int n,int m,int value)
    49. {
    50. Map<String,Integer> date = new HashMap<String,Integer>();
    51. date.put("" + n + m,value);
    52. demo.add(date);
    53. }
    /*
    @author: jarg
    @TODO 动态规划 - 备忘录法 求解二项式系数
    */
    
    /* 求解二项式系数 */
    public static int Binomial(int n,int m)
    {
    	/* 边界条件 */
    	if(n==m || m==0)
    	{
    		return 1;
    	}
    
    	int date = readDate(n,m);
    	if(date>0)
    	{
    		/*
    		子问题已经计算过
    		读取保存在备忘录中的数据
    		*/
    		return date;
    	}
    	else
    	{
    		/*
    		子问题未计算过
    		解出子问题,将数据保存在备忘录中
    		*/
    		int result = Binomial(n-1,m) + Binomial(n-1,m-1);
    		writeDate(n,m,result);
    		return result;
    	}
    }
    
    /* 从备忘录中读取数据 */
    public static int readDate(int n,int m)
    {
    	for(int i=0;i<demo.size();i++)
    	{
    		Map<String,Integer> date = new HashMap<String,Integer>();
    		date = demo.get(i);
    		if(date.get("" + n + m) != null)
    		{
    			return date.get("" + n + m);
    		}
    	}
    	return 0;
    }
    
    /* 向备忘录中写入数据 */
    public static void writeDate(int n,int m,int value)
    {
    	Map<String,Integer> date = new HashMap<String,Integer>();
    	date.put("" + n + m,value);
    	demo.add(date);
    }
    

    2. 动态规划 迭代法:

    迭代法采用自底向上方式,保存已求解的子问题,需要时取出,消除对某些子问题的重复求解.

    Pascal三角形:


    说明: 在非边界的情况下,二项式系数=上一行同列数值+上一行同列前一个数值.

    为了节省空间,根据n的大小,定义长度为n+1的整型数组,用以存储子问题的解.

    从后往前计算图中二项式系数的解,完成后,将问题解存储在数组中对应的列标号位置.

    Java代码 复制代码 收藏代码
    1. /*
    2. @author: jarg
    3. @TODO: 动态规划 - 求解二项式系数
    4. */
    5. /* 求二项式系数 */
    6. public staticint binomial(int n,int m)
    7. {
    8. int value[] = newint[n+1];
    9. for(int i=0;i<=n;i++)
    10. {
    11. value[i] = 1;
    12. /* 边界条件m=0,n=m的情况 */
    13. for(int j=i-1;j>0;j--)
    14. {
    15. value[j] = value[j] + value[j-1];
    16. }
    17. }
    18. return value[m];
    19. }
    展开全文
  • 自底向上设计

    千次阅读 2004-11-02 16:07:00
    向 上 设 计 邓 辉 (翻译) 长期以来,我们一直遵循这样一个编程风格方面的原则:一个程序的功能要素不应该太大。如果程序中的某些部件的规模超出了易于理解的范围,就会造成大量的复杂性,这些复杂性很容易...
  • 自底向上顶向下的架构设计区别

    万次阅读 多人点赞 2020-09-16 22:32:48
    某日小明上数学课,他的老师给了很多个不同的直角三角板让小明用尺子去量三角板的三个边,并将长度记录下来。两个小时过去,小明完成任务,把数据拿给老师。老师给他说,还有一个任务就是观察三条边之间的数量关系。...
  • 顶向下测试 目的:从顶层控制(主控模块)开始,采用同设计顺序一样的思路对被测系统进行测试,来验证系统的稳定性。 定义:顶向下的集成测试就是按照系统层次结构图,以主程序模块为中心,自上而下按照深度...
  • 详细的自底向上分析法的解读 LR构造分析表 LR分析表的结构如上,其分为两个部分Action Goto Action 两个参数状态i,终结符号a(s(i)代表第i个状态,r(i)代表第i条表达式) 移入j:j是一个状态,把j压入栈(同时移...
  • 项目的深入理解需要顶向下与自底向上的学习

    千次阅读 热门讨论 2012-08-05 10:18:14
    项目的学习需要持续不断的顶向下的学习与自底向上的学习。何谓顶向下的学习,即先着手系统架构,然后逐层进入业务模块,最后进入细粒度功能模块的开发。所谓自底向上的学习,就是先从一行代码,一个Bug,一个...
  • 顶向下和自底向上测试的优缺点

    千次阅读 2017-03-09 16:21:06
    顶向下测试方法的主要优点是不需要测试驱动程序,能够在测试阶段的早期实现并验证系统的主要功能,而且能在早期发现上层模块的接口错误。...自底向上测试方法的优缺点与上述顶向下测试方法的优缺点刚好相反
  • 顶向下的集成是从主控模块(主...自底向上的集成是从最底层模块(即叶子结点)开始,按照调用图的结构,从下而上,逐层将各模块组装起来。在从下而上的集成测试环境中,需对那些未经集成测试的模块开发驱动模块...
  • 信息系统开发的发展过程经历过所谓“自底向上”方式和“顶向下”方式,从整体上分析和总结了两种方法的优缺点。  自底向上方法的优点有:  有助于发现和理解每个系统的附加需要,并易于判断其费用  相对...
  • 自底向上的分析技术 有: ( 1 )简单优先分析法 ( 2 )算符优先分析法 ( 3 )优先函数 ( 4 ) LR 分析法 首先注意一点:无论是那种语法分析,语法都是从左至右的读入符号!  自底向上分析法,也称移进-归约分析...
  • 顶向下测试和自底向上测试

    千次阅读 2015-08-19 16:43:41
    顶向下测试:是从程序的初始模块开始测试。 (1)该方法会在早期发现顶层的错误。 (2)早期的程序框架可以进行演示 (3)需要开发桩模块辅助...自底向上测试:是从程序的底层模块开始测试。 (1)I/O操作可以
  • 按照归并顺序的不同,归并排序可以分为顶向下和自底向上两类。顶向下的归并排序进行的操作主要就是对数组的拆分与合并。通过层层拆分得到单元素数组,天生有序,然后归并两个单元素数组得到一个较大的有序数组,...
  • 层次聚类——自底向上方法

    千次阅读 2016-09-04 22:51:44
    直观认识 假设数据集D={a,b,c,d,e}D=\{a, b, c, d, e\}, 在D上运行自底向上的层次聚类算法的过程如下图所示:
  • 算法之自底向上的归并排序

    千次阅读 2016-05-20 23:00:57
    之前使用顶向下的归并排序,我们的主要思想是将一个大问题分成一个小问题,通过解决一个一个小问题来最终完成大问题。既然我们可以通过化整为零的方式Coding,那么是不是也可以由简入繁,由下到上? 仔细一想,...
  • 自底向上的执行 软件测试 小规模程序: 直接执行 中等规模:底层开始, 逐步上升, 运行基本方法, 测试整体函数 较大规模:高级软件测试方法 软件工程:  系统、严格约束, 可量化的方法, 应用于软件的
  • _01背包问题_自底向上法_动态规划_

    千次阅读 2018-01-15 14:58:37
    今天记录一下我所理解的01背包问题动态规划求解思路 思路如下 m代表背包承重 wp代表物品重量和物品价值数组 设置全局变量result数组记录当前重量和存放物品个数最大价值 两个for从1开始遍历,设置0位置默认为0 ...
  • 自底向上的语法分析

    千次阅读 2018-06-11 18:46:14
    自底向上分析中,分析过程的每一步都是从当前句型中选择一个可归约的子串,将它归约到某个非终结符号 实现自底向上分析最常用的技术就是移进-规约分析,边移入边分析,一旦栈顶符号串形成某个句型的句柄或其他可...
1 2 3 4 5 ... 20
收藏数 107,229
精华内容 42,891
关键字:

自底向上