精华内容
下载资源
问答
  • 动态规划备忘录算法
    千次阅读
    2016-05-13 14:30:33

    备忘录算法是用C[i,j]记录下目前已经”走过的路”
    动态规划是自底而上的根据重复次数”走路”的一种规律?

    更多相关内容
  • 动态规划备忘录

    千次阅读 2015-11-04 21:04:58
    动态规划与分治方法相似,都是通过组合子问题的解来求解原文题。分治方法将问题划分为互不相交的子问题,递归地...而动态规划算法对每个子子问题只求解一次,将其解保存在一个表格中,从而无需每次求解一个子子问题时都

    动态规划与分治方法相似,都是通过组合子问题的解来求解原问题。分治方法将问题划分为互不相交的子问题,递归地求解子问题,再将它们的解组合起来,求出原问题的解。与之相反,动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题。在这种情况下,分治算法会做许多不必要的工作,它会反复地求解那些公共子子问题。而动态规划算法对每个子子问题只求解一次,将其解保存在一个表格中,从而无需每次求解一个子子问题时都重新计算,避免了这种不必要的计算工作。
    虽然动态规划算法对每个子子问题只求解一次,但某些子问题在对求解最优解的过程中并无影响,从而不必去求解这类子问题。这里,可以使用备忘录法。
    大体思想是:先将每个子问题设为一特定值(如∞)。在求解最优解过程中,当要用到某个子子问题的解时,再去对其进行求解。这种方法可以避免对所有子问题都进行求解,从一定程度上节省了时间开销。

    展开全文
  • 递归算法是一类非常常用的算法,它是一种直接或间接调用原算法本身的算法。递归算法最大的特点就是“自己调用自己”,对于一些具有递归特性的问题,使用递归算法来解决会更加简单明了,且易于实现。 在使用递归算法...
    • 递归:

            递归算法是一类非常常用的算法,它是一种直接或间接调用原算法本身的算法。递归算法最大的特点就是“自己调用自己”,对于一些具有递归特性的问题,使用递归算法来解决会更加简单明了,且易于实现。

            在使用递归算法解决实际的问题时,要自顶向下地将一个大问题拆分成同类的小问题,然后利用同类问题这一特性构造出解决问题的递归函数,也就是这种“自己调用自己”的模型,再通过程序实现这个递归函数。

    图片

             下面通过一个实例理解递归算法。

            走楼梯问题:一个楼梯共有10级台阶,一个人从下往上走,他可以一次走一个台阶,也可以一次走两个台阶。请问这个人有多少种走法走完这10级台阶?

            这是一道经典而有趣的算法题,本题有很多种解法,其中最为经典而简洁的解法是使用递归算法解决。我们先来看一下如何使用递归法求解此题。

            因为这个人一次可以走一个台阶,也可以走两个台阶,所以他可以有很多种组合方法走完这10级台阶。例如可以如图(1)所示这样上楼:

            走法一:1--> 1-->1--> 1-->1--> 1-->1--> 1-->1--> 1,如图(1)所示:

    图片

    也就是每步都走一个台阶。

    可以如图(2)所示这样上楼:

    走法二:2-->1--> 1-->1--> 1-->1--> 1-->1--> 1,如图(2)所示。

    图片

            也就是先上两级台阶,再一步一个台阶地上8个台阶。

            这样看来,这个人可以有很多种方式走完这10个台阶,那么我们要如何计算共有多少种走法呢?

            试想如果这个人要走到第10级台阶,必然存在且仅存在以下两种情形:

            (1)此人先登到第8级台阶上,然后在第8级台阶处向上直接登2个台阶,而不经过第9级台阶,如图(3)所示;

     (2)此人登上了第9级台阶,再向上登1级台阶即可到顶,如图(4)所示。

    图片

             有的读者可能会有这样的质疑:“此人在第8级台阶处向上登1级台阶到第9级台阶上,然后再向上登1级台阶到第10级台阶,这也是一种情形啊?”其实这种场景已经包含在第2种情形之中了,第1种情形与第2种情形是以是否登到第9级台阶上作为划分的,只要登到第9级台阶之上就都属于第2种情形。

            因为这个人一次只能走一个台阶或者两个台阶,所以此人要登到第10级台阶上只可能存在上述两种可能,所以这种划分是完备的。

            假设这个人登到第8级台阶(第1种情形)的走法有x种,登到第9级台阶(第2种情形)的走法有y种,很显然,此人登上10级台阶的走法共有x+y种。

            我们用F(10)表示这个人登上10级台阶总共的走法,用F(9)表示他登上9级台阶总共的走法,用F(8)表示他登上8级台阶总共的走法,则有F(10)=F(9)+F(8)。不难想象,类比F(10)的计算,我们可以得到F(9)的计算公式:F(9)=F(8)+F(7)以及F(8)的计算公式:F(8)=F(7)+F(6),……,依此类推。当只有1级台阶时其走法只有1种,所以F(1)=1;当只有2级台阶时其走法只有2种,所以F(2)=2。所以我们可以总结出计算F(n)的公式:

    图片

            不难看出这是一个递归公式,所以可以使用递归算法求解此题。求解此题的Java代码实现如下:

    public class ClimbStairs {
    
        private static int getClimbWays(int n) {
    
            if (n == 1) {
    
                return 1;
    
            } else if (n == 2) {
    
                return 2;
    
            } else {
    
                return getClimbWays(n-1) + getClimbWays(n-2);
    
            }
    
        }
    
         public static void main(String []args) {
    
            int climbWays = 0;
    
            climbWays = getClimbWays(10);
    
            System.out.println("There are "+ climbWays + " ways to climb 10 steps ");
    
        }
    
    }

            代码中函数getClimbWays()是一个递归函数,它的作用是返回登上n级台阶总共的走法数。在函数getClimbWays()内部会判断n的值,当进行到某一层递归调用中n的值变为1或者2时,该函数即可返回1或2,此为该递归调用的出口。如果n的值不等于1或2,则递归地调用getClimbWays()函数,返回getClimbWays(n-1) + getClimbWays(n-2)的值即为本题的答案。上述代码的执行结果如图(5)所示。

    图片

            如图(5)所示,登上10级台阶共有89种走法。

            深入思考上面这个递归算法不难发现,该算法其实存在着很多冗余的计算。因为我们在计算F(n)时首先要计算F(n-1)和F(n-2),而计算F(n-1)时又要先计算F(n-2)和F(n-3),这样F(n-2)就计算了两遍。对应到上面的代码,就是函数getClimbWays()会执行很多次重复冗余的调用,我们可以通过图(6)直观地看到这一点。

    图片

            如图(6)所示,深蓝色框中的函数只需要调用一次即可,而在这棵递归树中每一个方框中的函数都会被调用到,所以使用递归算法解决本题会存在这大量的冗余计算。

            这也就是递归算法的一大缺点——重复冗余的计算。如果递归函数中存在多次递归调用的情形(例如这里的F(n-1)+F(n-2)),则势必存在这种重复计算的情况。这也是导致递归算法性能不高的一个重要原因。

    • 备忘录:

             如何解决重复计算的问题呢?直观的想法是,我们可以将计算得到的中间结果保存在一个叫做“备忘录”的结构中,这样再次执行相同的计算过程时,就没有必要真的计算了,而是直接从“备忘录”中取出记录下来的结果,这样的性能会比单纯地使用递归调用高很多。

    图片

        下面给出备忘录方法的代码实现。

    public class ClimbStairs {
    
        private static HashMap<Integer,Integer> memorandum
    
        = new HashMap<Integer,Integer>();
    
        private static int count = 0;
    
        
    
        private static int getClimbWays(int n) {
    
            count++;
    
            if (n == 1) {
    
                return 1;
    
            } else if (n == 2) {
    
                return 2;
    
            } else {
    
                Integer rec1 = memorandum.get(n-1);
    
                Integer rec2 = memorandum.get(n-2);
    
                if (rec1 == null) {
    
                    rec1= getClimbWays(n-1);
    
                    memorandum.put(n-1,rec1);
    
                }
    
                if (rec2 == null) {
    
                    rec2 =  getClimbWays(n-2);
    
                    memorandum.put(n-2,rec2);
    
                }
    
                return rec1+rec2;
    
            }
    
        }
    
         public static void main(String []args) {
    
            int climbWays = 0;
    
            climbWays = getClimbWays(10);
    
            System.out.println("count = " + count);
    
            System.out.println("There are "+ climbWays +
    
                                      " ways to climb 10 steps ");
    
        }
    
    }

            在上述代码中,在类ClimbStairs 中定义了一个HashMap类型的成员memorandum,这就是所谓的备忘录。在函数getClimbWays(int n)中,如果参数n>2,则先尝试从memorandum中获取key为n-1和n-2的value,也就是getClimbWays(n-1)和getClimbWays(n-2)的值,这样就省去了每次都要递归调用函数getClimbWays()的消耗。如果获取的值为null,则说明还没有还没有执行getClimbWays()函数,因此需要执行一次getClimbWays()函数,并将返回的结果以键值对<key,value>的形式保存到memorandum中,以便下一次使用时可直接从备忘录中获取。

            另外,为了计算备忘录方法可以减少多少次递归函数getClimbWays()的调用,我们定义了一个计数器变量count,并在进入函数getClimbWays()时将count自动加1,以便统计调用的次数。实验证明,调用计算10级台阶的走法getClimbWays(10),使用单纯的递归方法,需调用函数getClimbWays()共109次,而使用备忘录方法则仅需调用函数getClimbWays()共17次!

    • 动态规划:

            那么有没有一种更为高效的算法来解决这个问题呢?无论是递归算法还是备忘录算法,其本质都是一种自顶向下的运算方式,也就是从F(10)开始逐级分解该问(F(9),F(8),F(7)……),重复调用自身过程的同时问题的规模不断缩小。其实我们还可以自底向上的运算,也就是从F(1)=1,F(2)=2计算出F(3)=3,再从F(2)=2,F(3)=3计算出F(4)=5,……以此类推,一直求到F(n)。由于采用这种方式可将每一步的计算结果都记录下来,所以在这个过程中没有任何冗余的运算,算法的效率会高很多。同时运算的过程中没有任何递归调用,在一定程度上也消除了因递归调用而带来的系统开销。我们称这种利用问题本身的递归特性,自底向上逐级迭代计算出最优解的方法为动态规划算法。

    走楼梯问题动态规划算法的Java代码实现如下。

    public class ClimbStairs {
    
         private static int getClimbWays(int n) {
    
            int a = 1;
    
            int b = 2;
    
            int tmp = 0;
    
            int i = 0;
    
            if (n == 1) {
    
                return 1;
    
            } else if (n == 2) {
    
                return 2;
    
            } else {
    
                for (i=3; i<=n; i++) {
    
                    tmp = a + b;
    
                    a = b;
    
                    b = tmp;
    
                }
    
                return tmp;
    
        } 
    
    }
    
    
    
         public static void main (String[] args) {
    
            int climbWays = 0;
    
            climbWays = getClimbWays(10);
    
            System.out.println("There are "+ climbWays + " ways to climb 10 steps ");
    
    
    
        }
    
    }

            上述代码中函数getClimbWays()的作用是返回登上n级台阶总共的走法数。当n等于1时表示只有一个台阶,此时只有一种走法,所以函数返回1;当n等于2时表示只有2个台阶,此时只有两种走法,所以函数返回2;否则需要通过一个循环来计算共有多少种走法。该循环就是上面所讲的自底向上的求解过程,即通过初始值a=1(F(1)的值)和b=2(F(2)的值)来计算F(3),进而计算F(4),F(5),……,直到计算出F(n),并将其返回。上述代码的执行结果如图(7)所示。

    图片

            显然,使用动态规划算法计算的结果与使用递归算法计算的结果是相同的。

    • 总结:        

            通过上面这个实例,相信大家对动态规划算法能有一个比较直观的理解。动态规划算法与递归算法的相似之处在于动态规划算法也是将一个规模较大的问题分解为规模较小的问题,然后逐一求解再汇聚成一个大的问题,但不同之处是动态规划算法是以自底向上的方式计算最优解,而递归法和备忘录法则都采用自顶向下的方式,备忘录法只是在递归法的基础上增加了“备忘录”数据结构,从而减少了冗余的递归调用。因此动态规划算法可以在计算过程中保存已解决的子问题答案,每个子问题只计算一次,这样可以减少冗余的计算,提高解决问题的效率。

            在使用动态规划算法解决问题时要把握两个基本要素,它们分别是:

    •  具备最优子结构
    •  具备子问题重叠性质

            只有当一个问题具备了这两个基本要素才能使用动态规划算法来求解。

            设计动态规划算法的第一步通常是要刻画出问题的最优子结构。当一个问题的最优解包含了其子问题的最优解时,就称该问题具有最优子结构性质。以走楼梯问题为例,我们首先可以归纳出该问题的递归公式,即F(n)=F(n-1)+F(n-2),n>2,那么F(n-1)和F(n-2)就是F(n)的最优子结构,因为F(n-1)和F(n-2)是F(n)子问题的最优解。

            另外使用动态规划算法求解的问题还应具备子问题的重叠性质。以上面这个走楼梯问题为例,在递归算法中每次产生的子问题并不一定总是新问题,很多子问题都需要被反复的计算多次,就像图(6)中所示的那些方框中的函数调用。而动态规范算法正是利用了这种子问题重叠的性质,采用自底向上的方式计算,每个子问题只计算一次,然后将结果保存到变量(例如上述代码中的变量a,b,tmp)中或者表格中(可以使用数组等数据结构来存储),当再次使用时只需要查询并读取即可,这样可以提高解题的效率。

             “爬楼梯”问题是一道非常简单的既可用递归法,也可用动态规划算法求解的问题。之所以用这样一个简单的问题来解释递归、备忘录和动态规划,目的就是为了让大家更多地关注递归、备忘录和动态规划的本质,从而更加轻松地理解这些算法的内涵和使用场景。在后续的文章中,我会讲解一些更为复杂的问题。但是万变不离其宗,只要掌握了递归、备忘录和动态规划的本质和它们之间的区别,很多看似复杂的问题其实也都不难解决。

    想要阅读更多算法面试类精选文章,可关注我的微信公众号 @算法匠人

     

    展开全文
  • 使用备忘录方法解决0-1背包问题: 1.跟直接递归很相似,该算法能将递归遇到的子问题的解保存在一个表中,以便下一个递归遇到同样的子问题时快速求解。...3.备忘录算法动态规划算法的区别有:
    使用备忘录方法解决0-1背包问题:
    1.跟直接递归很相似,该算法能将递归遇到的子问题的解保存在一个表中,以便下一个递归遇到同样的子问题时快速求解。

    2.为了区分一个子问题是否已经求解,可以通过查表的方式来判断,若子问题对应的表中元素的值为一个初始特殊值,说明该子问题还未求解;否则,表明该子问题曾经已求解过,直接获取子问题的解,不需要递归求解该值。

    3.备忘录算法与动态规划算法的区别有:

    (1)备忘录方法的递归方式是自顶向下,而动态规划算法则是自底向上递归的。

    (2)备忘录方法的控制结构与直接递归方法的控制结构相同,而动态规划算法的控制结构与循环迭代的控制结构相同。

    (3)备忘录方法为每个解过的子问题建立了备忘录以备需要时查看,避免相同子问题的重复求解;而动态规划算法则是建立一个表格,从最小的子问题开始向上求解较大的子问题,把每一个子问题的解全部填入表格中,直到表格中出现原问题的解为止。它们两者的共同特点是对子问题的求解都只解了一次,并记录了答案。

    (4)当一个问题的所有子问题都至少要解一次时,用动态规划比用备忘录方法要好,此时,动态规划算法没有任何多余的计算。当子问题空间中的部分问题可不必求解时,用备忘录方法较有利,因为从其控制结构可以看出,该方法只解那些确实需要求解的子问题。


    以下是源代码:

    #include "stdafx.h"
    #include <iostream>
    #include <ctime>
    using namespace std;
    
    const int N = 4; //物品数量
    const int C = 7; //背包容量
    int w[N] = {2,3,5,2};
    int v[N] = {6,4,8,4};
    int m[N][C+1]; //记录子问题的解的表格
    int x[N];
    
    void initial()
    {
    	for (int i = 0; i < N; i++)
    	{
    		for (int j = 0; j <= C; j++)
    		{
    			m[i][j] = -1;
    		}
    	}
    }
    
    //以下使用备忘录法求解0-1背包问题(物品重量为整型)
    int KnapsackMemoMethod(int i, int capacity)
    {
    	if(m[i][capacity] != -1)
    		return m[i][capacity]; //使用m[i][capacity]需要检查两个下标是否出界
    	int result = 0;
    	if(i == N-1)
    		if(capacity >= w[i])
    		{
    			m[i][capacity] = v[i];
    			return v[i];
    		}			
    		else
    		{
    			m[i][capacity] = 0;
    			return 0;
    		}
    
    	else
    	{
    		if(capacity >= w[i])
    		{
    			int selected = KnapsackMemoMethod(i+1,capacity-w[i])+v[i];
    			int unselected = KnapsackMemoMethod(i+1,capacity);
    			result = selected > unselected ? selected : unselected;
    			m[i][capacity] = result;
    			return result;
    		}
    		else //capacity < w[i]
    		{
    			result = KnapsackMemoMethod(i+1,capacity);
    			m[i][capacity] = result;
    			return result;
    		}
    			
    	}
    }
    
    void Trace(int i, int capacity)
    {
    	if(i == N-1)
    	{	
    		if(m[i][capacity] == v[i])
    			x[i] = 1;
    		else
    		{
    			x[i] = 0;
    		}
    		return;
    	}
    	else
    	{		
    		if (m[i][capacity] == m[i+1][capacity])
    		{
    			x[i] = 0;
    			Trace(i+1, capacity);
    		}
    		else
    		{
    			x[i] = 1;
    			Trace(i+1, capacity - w[i]);
    		}
    	}	
    }
    
    int main()
    {
            initial();
    	cout<<KnapsackMemoMethod(0,C)<<endl;
    	Trace(0,C);
    	for (int i = 0; i < N; i++)
    	{
    		cout<<x[i]<<" ";
    	}
    	cout<<endl;
    	system("pause");
    	return 0;
    }

    运行结果如下:

    14

    1 0 1 0

    展开全文
  • 动态规划备忘录方法的区别 动态规划算法的基本要素: 1 最优子结构性质 当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。 2 重叠子问题性质 动态规划算法对每个问题只解一次,将其解保存在...
  • 分治,动态规划备忘录搞不清,遇到问题不知道应该用什么样的方法合适? 分治:分治算法对问题进行分解时所遵循的原则是将待求解问题分解为若干个规模较小、相互独立且与原问题相同的子问题(不包含公共的子问题...
  • //矩阵连乘的动态规划算法#include using namespace std;long MaxtrixChain1(int n);long MaxtrixChain1(int i, int j);int const MAX = 1000;long subMatrixChain[MAX][MAX];int bestK[MAX][MAX];int dim[MAX];int ...
  • 备忘录算法

    2014-03-22 15:51:42
    这是一个用C++做备忘录算法,备忘录方法是动态规划方法的变形。与动态规划算法不同的是,备忘录方法的递归方式是自顶向下的,而动态规划算法则是自底向上的
  • 0-1背包问题(动态规划算法) 文章目录0-1背包问题(动态规划算法)一、思路 一、思路 我们直接从一个实例开始。 有五件商品,如下表,vi代表它的重量,pi代表它的价值,背包容量为13。 第一步,初始化备忘录表。 ...
  • 动态规划:0-1背包问题(递归+备忘录)
  • 在我们的课程设计、大作业中会涉及到挖金矿问题,今天我用备忘录算法解决,可以得到最优解,便于帮助你们。 //有一个国家发现了5座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。 //参与挖矿工人的...
  • 动态规划&备忘录方法&递归方法

    千次阅读 2015-10-29 21:08:39
    动态规划的基本思想是,将原问题拆分为若干子问题,自底向上的求解。其总是充分利用重叠子问题,即通过每个子问题只解一次,把解保存在一个表中,巧妙的避免了子问题的重复求解。 递归方法,采用的是自顶向下的...
  • 矩阵连乘备忘录算法湖南涉外经济学院 计算机科学与技术专业《算法设计与分析》课程矩阵连乘备忘录算法实 验 报 告班级:学号:姓名:教师:成绩:2012年5月【实验目的】1 掌握动态规划算法和2 利用动态规划思想实现3...
  • 备忘录动态规划算法的变形﹒备忘录方法也是用表格保存已解决子问题的答案﹒ 与动态规划算法不同的是,备忘录方法的递归方式是自顶向下的,而动态规划算法则是自底向上递归的.因此,备忘录方法的控制结构与直接递归...
  • 动态规划解题思路 矩阵链构造函数:构造m[][]和s[][] m中存储的值是计算出来的最小乘法次数,比如m[1][5]就是A1A2A3A4A5的最小乘法次数 s中存储的是获取最小乘法次数时的断链点,s[1][5]对应的就是如何拆分A1A2A3A4...
  • 大家都知道,数值稍大的递归运行时间对于开发者来说就是场灾难,我们总是想方设法在优化递归,或者说不用递归,此文中从空间时间角度详细剖析以上三种算法的区别,以及运行原理,以斐波那契数为例, 编程语言java ...
  • 动态规划算法的基本要素:1最优子结构性质当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。2重叠子问题性质动态规划算法对每个问题只解一次,将其解保存在一个表格中,当再次需要解此问题时,...
  • 题目: 有N件物品和⼀个最多能被重量为W 的... 动态规划五部曲: 1.确定dp数组以及下标的含义 使⽤⼆维数组,即dp[i][j] 表示从下标为[0-i]的物品⾥任意取,放进容量 为j的背包,价值总和最⼤是多少。 2. ...
  • 设计一个求解该问题的算法,给出算法的伪码描述并分析算法的时间复杂度.假设问题的输入实例是:v1=1,v2=4,v3=6,v4=8w1=1,w2=2,w3=4,w4=6y=12给出算法在该实例上计算的备忘录表和标记函数表并说明付钱的方法。
  • 动态规划:最大子段和(递归+备忘录)
  • 矩阵链乘的备忘录算法,输入多个矩阵,输出需要乘法计算次数最少的分割结果
  • 动态规划系列—动态规划VS回溯算法

    千次阅读 2020-09-19 16:14:20
    动态规划和回溯算法看起来有挺多共同之处,都涉及到了【递归】和【做选择】,那么他们之间区分在哪里呢?以及这两者之间是否能够转化? 通常来讲,我们使用回溯算法去遍历的时候,就是在使用暴力穷举的方法,当数据...
  • 动态规划法——斐波那契数列(备忘录
  • 加了备忘录的自顶向下的递归算法备忘录动态规划) 将每一个子问题的结果记录在一个备忘录表中;下次再遇到时直接先查备忘录;没有再递归算法 代码 src/samples/algorith/C153MemoizedMatrixChain.ts · Bob/...
  • 问题描述: 一共有十级台阶,每一次只能上1级或2级,问一共有多少种上台阶的方法。 解析: 这个问题可以从一阶、两阶、三阶来入手。...因此很容易就可以写出一个递归的算法 int get(int n) {//递归 if(n<1) retu
  • 动态规划中,由于会运用到数学归纳法的思想(通过子问题的答案推出大问题的答案),我们常常使用递归的方式来解决此类问题。但在递归过程中常常会重复求出子问题的答案,这是很浪费时间的,所以我们可以考虑能否用...
  • 算法备忘录法(记忆化搜索)

    千次阅读 2020-11-11 22:18:52
    备忘录法是为了解决避免分治算法中相同子问题的重复求解。 备忘录法为每个解过的子问题建立备忘录以备需要时查看,所以也称搜表法。 备忘录法的控制与直接使用递归方法的控制结构相同。 备忘录法又称记忆化搜索,自...
  • 对比备忘录方法(递归)和动态规划(递推) 备忘录方法 备忘录方法要用递归实现 递归是自顶向下的解决问题的:即从目标开始,将问题划分,对子问题求解,直到边界 递归前对备忘录进行查询,当前备忘录未被填写时,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,167
精华内容 12,066
关键字:

动态规划备忘录算法

友情链接: krat.zip