精华内容
下载资源
问答
  • 动态规划递归算法

    2020-06-14 23:36:46
    1. 使用递归算法 我们需要判断改题目是否由多个子任务组成,可以嵌套成递归的形式,在这一步我们往往需要一个递归表达式。 当有中间状态时 有时候我们在处理路径搜索,有中间状态如状态矩阵时,我们需要设定一个容器...

    假定有一个LeetCode题目

    1. 使用递归算法

    我们需要判断改题目是否由多个子任务组成,可以嵌套成递归的形式,在这一步我们往往需要一个递归表达式。

    当有中间状态时

    有时候我们在处理路径搜索,有中间状态如状态矩阵时,我们需要设定一个容器存储中间状态的数值。一般我们会设定一个与初始矩阵同等大小的矩阵作为容器。更新路径的信息。

    2.使用动态规划Dynamic Programming

    动态规划是一种多阶段决策最优解的模型,一般用以求最值。可用于自下而上的递推求解。

    使用动态规划要满足三个条件:

    1. 多阶段决策
    2. 最优子结构
    3. 自下而上(求状态转移方程)

    基本思路

    1. 首先判断是否可使用递归法求解,并列出递归法的树状图
    2. 再判断在递归的过程中是否存在大量的重复计算的子问题,假如存在重复问题,说明使用递归法会有大量的重复计算,影响效率
    3. 然后用备忘录记录子问题与其计算记录(记录中间状态)
    4. 最后改用自下而上的方法重新递推,得到的解法即为动态规划
    展开全文
  • 斐波那契数 1,1,2,3,5,8,13,21….... ...斐波那契公式为: ...\left\{ \begin{aligned} & F(0)=F(1)=0 \\ & F...从计算第40个斐波那契数可以明显看出,采用动态规划的方式计算速度远远快于采用递归的方式计算。

    斐波那契数

    • 1,1,2,3,5,8,13,21….从第3个数开始,每个数等于它前面的两个数之和。
    • 斐波那契公式为:
      {F(0)=F(1)=0F(n)=F(n1)+F(n2)  n3

    递归算法

    • 从公式中能看出,可以采用递归的算法算第n个斐波那契数的值。
    • 递归基准条件(终止条件)为 n==0或1。
    int Fabonacci(int n)
    {
        if (n <= 1)
            return 1;
        else
            return Fabonacci(n - 1) + Fabonacci(n - 2);
    }

    算法评价

    • 斐波那契数递归算法是递归应用的一个不好的例子。
    • 原因在于,每次计算都要执行两次递归,而且两次递归产生了大量的重复计算。
    • 例如要计算F(4):那么要计算出F(3)和F(2),F(3)通过F(2)和F(1)计算返回,F(3)的F(2)通过F(1)和F(0)计算返回,F(4)的F(2)通过F(1)和F(0)计算返回。整个过程F(0)计算2次、F(1)计算3次、F(2)计算2次、F(3)和F(4)分别计算1次。
    • 大量重复的计算,使得复杂度呈指数爆炸增长。

    动态规划的算法

    • 动态规划的算法把原问题分成一个个子问题,记录子问题的解来求原问题的解。
    • 例如:

      F(n)=F(n1)+F(n2)  n3

    • 每次记录子问题F(n-1)和F(n-2),下次就能直接拿来计算F(n)。

    • 动态规划也有基准即子问题的边界,这里和递归一样F(0)=F(1)=0。
    int FabonacciD(int n)
    {
        int Fa = 1;     // 初始化Fa=1,Fa为要求第n个数值的前两位数即n-2个数值
        int Fb = 1;     // 初始化Fb=1,Fb为要求第n个数值的前一位数即n-1个数值
        int Fab = 0;
        for (int i = 2;i <= n;i++)
        {
            Fab = Fa + Fb;  // Fab 每次由位于它之前的两个斐波那契数相加
            Fa = Fb;        // 更新Fa数值为原来的Fb
            Fb = Fab;       // 更新Fb数值为原来的Fab
        }
        return Fab;
    }

    算法评价

    • 每个F(n)只需计算一次然后记录下来,避免了大量重复的计算。
    • 动态规划通过牺牲空间复杂度来换取时间复杂度的降低。单大多情况下牺牲是值得的。

    附斐波那契数两种计算方式及运行时间比较C++

    #include<iostream>
    #include<ctime>
    
    using namespace std;
    
    int Fabonacci(int n)
    {
        if (n <= 1)
            return 1;
        else
            return Fabonacci(n - 1) + Fabonacci(n - 2);
    }
    
    int FabonacciD(int n)
    {
        int Fa = 1;     // 初始化Fa=1,Fa为要求第n个数值的前两位数即n-2个数值
        int Fb = 1;     // 初始化Fb=1,Fb为要求第n个数值的前一位数即n-1个数值
        int Fab = 0;
        for (int i = 2;i <= n;i++)
        {
            Fab = Fa + Fb;  // Fab 每次由位于它之前的两个斐波那契数相加
            Fa = Fb;        // 更新Fa数值为原来的Fb
            Fb = Fab;       // 更新Fb数值为原来的Fab
        }
        return Fab;
    }
    
    int main()
    {
        int n = 40;
        clock_t start, finish;
        cout << "NO." << n << "'s Fabonacci number in a recursion way:\n";
        start = clock();
        cout << Fabonacci(n) << endl;
        finish = clock();
        cout << "Cost Time: ";
        cout << static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
    
        cout << "NO." << n << "'s Fabonacci number in a Dynamic programming way:\n";
        start = clock();
        cout << FabonacciD(n) << endl;
        finish = clock();
        cout << "Cost Time: ";
        cout << static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
        system("pause");
    
        return 0;
    }
    • 运行结果
    NO.40's Fabonacci number in a recursion way:
    165580141
    Cost Time: 3980ms
    NO.40's Fabonacci number in a Dynamic programming way:
    165580141
    Cost Time: 0ms
    请按任意键继续. . .
    • 从计算第40个斐波那契数可以明显看出,采用动态规划的方式计算速度远远快于采用递归的方式计算。
    展开全文
  • 一般实际生活中我们遇到的算法分为四类: 一>判定性问题 二>最优化问题 三>构造性问题 四>计算性问题 ...动态规划 贪心算法 适用类型 通用问题 优化问题 优化问题
     
    

    一般实际生活中我们遇到的算法分为四类:

    一>判定性问题

    二>最优化问题

    三>构造性问题

    四>计算性问题

    而今天所要总结的算法就是着重解决 最优化问题

    《算法之道》对三种算法进行了归纳总结,如下表所示:

    标准分治

    动态规划

    贪心算法

    适用类型

    通用问题

    优化问题

    优化问题

    子问题结构

    每个子问题不同

    很多子问题重复(不独立)

    只有一个子问题

    最优子结构

    不需要

    必须满足

    必须满足

    子问题数

    全部子问题都要解决

    全部子问题都要解决

    只要解决一个子问题

    子问题在最优解里

    全部

    部分

    部分

    选择与求解次序

    先选择后解决子问题

    先解决子问题后选择

    先选择后解决子问题

    分治算法特征:

    1)规模如果很小,则很容易解决。//一般问题都能满足

    2)大问题可以分为若干规模小的相同问题。//前提

    3)利用子问题的解,可以合并成该问题的解。//关键

    4)分解出的各个子问题相互独立,子问题不再包含公共子问题。 //效率高低

    【一】动态规划:

    依赖:依赖于有待做出的最优选择

    实质:就是分治思想和解决冗余。

    自底向上(每一步,根据策略得到一个更小规模的问题。最后解决最小规模的问题。得到整个问题最优解)

    特征:动态规划任何一个i+1阶段都仅仅依赖 i 阶段做出的选择。而与i之前的选择无关。但是动态规划不仅求出了当前状态最优值,而且同时求出了到中间状态的最优值。

    缺点:空间需求大。

    【二】贪心算法:

    依赖:依赖于当前已经做出的所有选择。

    自顶向下(就是每一步,根据策略得到一个当前最优解。传递到下一步,从而保证每一步都是选择当前最优的。最后得到结果)

    【三】分治算法:

    实质:递归求解

    缺点:如果子问题不独立,需要重复求公共子问题

    展开全文
  • 递归算法转换为非递归算法

    千次阅读 2019-04-24 17:40:07
    对于某些复杂问题(例如hanio塔问题),递归算法是一种自然且合乎逻辑的解决问题的方式,但是递归算法的执行效率通常比较差。因此,在求解某些问题时,常采用递归算法来分析问题,用非递归算法来求解问题...

    转 自 : https://blog.csdn.net/fbz123456/article/details/50959412  
     

    递归算法实际上是一种分而治之的方法,它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题),递归算法是一种自然且合乎逻辑的解决问题的方式,但是递归算法的执行效率通常比较差。因此,在求解某些问题时,常采用递归算法来分析问题,用非递归算法来求解问题;另外,有些程序设计语言不支持递归,这就需要把递归算法转换为非递归算法。
        将递归算法转换为非递归算法有两种方法,一种是直接求值(迭代/循环),不需要回溯;另一种是不能直接求值,需要回溯。前者使用一些变量保存中间结果,称为直接转换法;后者使用栈保存中间结果,称为间接转换法,下面分别讨论这两种方法。

    1. 直接转换法
    直接转换法通常用来消除尾递归和单向递归,将递归结构用循环结构来替代。
    单向递归:简单的说是指递归的过程总是朝着一个方向进行,如果函数1调用了函数2,而函数2又调用了函数1,则这种情况不属于单向递归。斐波那契数列的递归求解可转用一个迭代法实现。

    斐波那契数列的递归求解:

    int Fib(int n) {
    if(n <= 1) return n;
    else return Fib(n - 1) + Fib(n - 2);
    }

    转化为迭代求解:

    int Fib(int n) {
    if(n <= 1) return n;
    int twoBack = 0;
    int oneBack = 1;
    int cur;
    for(int i = 2;i < = n; i++) {
       cur = twoBack + oneBack;
    twoBack = oneBack;
       oneBack = cur;
    }
    return cur;
    }

    尾递归函数是以递归调用结尾的函数,是单向递归的特例。它的递归调用语句只有一个,而且是放在过程的最后。当递归调用返回时,返回到上一层递归调用语句的下一语句,而这个位置正好是程序的结尾,因此递归工作栈中可以不保存返回地址;除了返回值和引用值外,其他参数和局部变量都不再需要,因此可以不用栈,直接采用循环写出非递归过程。

    阶乘函数就不是一个尾递归。因为在它收到递归调用的结果后,必须在返回调用前再做一次乘法运算。但是阶乘函数可以转化成一个尾递归函数,例:

    阶乘的递归求解:

    int factorial(int n)

    {
    if(n == 0) return 1;
    else

         {
    int val = factorial(n - 1);
    return n * val;
    }
    }

    转化为尾递归求解:

    int factorial(int acc, int x)

     { //acc传的值为1。
    if(x <= 1) return acc;
    else

         return factorial(x * acc, x - 1);
    }

    尾递归的重要性在于当进行尾递归调用时,调用者的返回位置不需要被存在调用栈里。当递归调用返回时,它直接分支到先前已保存的返回地址。因此,在支持尾递归优化的编译器上,尾递归在时间和空间上都比较划算。迭代算法需要一个临时变量,这无疑导致了程序的可读性降低,迭代函数不像递归函数那样需要考虑函数调用的支出,而且对一个线程来说可用的栈空间通常比可用的堆空间要少得多,而递归算法则相对迭代算法需要更多的栈空间!

    2. 间接转换法
    该方法使用栈保存中间结果,一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下:

    将初始状态s0进栈
    while (栈不为空)
    {
    退栈,将栈顶元素赋给s;
    if (s是要找的结果) 返回;
    else {
    寻找到s的相关状态s1;
    将s1进栈
    }
    }

    间接转换法在数据结构中有较多实例,如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等,请读者参考主教材中相关内容。
     

    展开全文
  • 递归算法向非递归算法转换

    千次阅读 2013-06-10 22:18:04
    递归算法实际上是一种分而治之的方法,它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题),递归算法是一种自然且合乎逻辑的解决问题的方式,但是递归算法的执行效率通常比较差。因此,在求解...
  • 递归算法

    千次阅读 2016-09-02 12:53:34
    递归算法的定义:递归过程一般通过函数或子过程来实现 递归算法解决问题的特点: (1) 递归就是在过程或函数里调用自身。 (2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。 (3) 递归算法解题...
  • 算法-递归算法

    千次阅读 2016-12-06 01:24:42
    递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。 本文主要从以下方面进行介绍递归算法: 1. 递归算法的概念 2. 递归算法的特点 3. 递归算法的应用 4. 递归...
  • 递归算法讲解

    万次阅读 多人点赞 2017-06-15 22:11:51
    原作者:书呆子Rico 《递归的内涵与经典应用》 http://my.csdn.net/justloveyou_摘要: 大师 L. Peter Deutsch 说过:To Iterate is Human, to ...对一些简单的递归问题,我们总是惊叹于递归描述问题的能力和编写代
  • 递归算法时间复杂度分析

    万次阅读 多人点赞 2018-09-17 16:16:59
    递归算法时间复杂度分析 时间复杂度: 一般情况下,算法中基本操作重复的次数就是问题规模n的某个函数f(n),进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用‘o’来表示数量级,给出算法时间复杂度。 T...
  • 汉诺塔问题的递归算法和非递归算法分析

    千次阅读 多人点赞 2020-03-11 12:13:04
    汉诺塔问题的递归算法和非递归算法分析 第一次发博客,想要以此记录自己的学习过程,也方便以后查看复习。希望能坚持下去。 问题描述 相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置...
  • (十六)递归算法递归算法应用

    千次阅读 2014-01-20 10:27:42
    若一个算法直接地或间接地调用自己本身,则称这个算法是递归算法。 问题的定义是递归的  例如:阶乘函数的定义  1 当n=1时   n! =   n*(n-1)! 当n>1时 递归算法的设计方法 适宜于用递归算法...
  • 递归算法与非递归算法比较

    千次阅读 2019-03-27 19:14:46
    递归效率高;递归代码写出来思路清晰,可读性强。 生成可执行文件大小应该和编译器有关吧。。。。 递归的话函数调用是有开销的,而且递归的次数受堆栈大小的限制。 以二叉树搜索为例: bool search(btree* p, ...
  • 本文介绍了递归算法和非递归算法的区别和转换
  • 斐波那契数列的表达式: F(1)=1 F(2)=1 F(n)=F(n-1)+F(n-2) (n>2) 递归算法:时间复杂度O(n^2) int recursive_method(int n) { if (n == 1 || n == 2) return 1; else return recursive_method
  • Java递归算法

    千次阅读 2015-08-23 22:55:27
    递归算法 其实就是程序的自身调用。在做递归算法的时候,必须要有一个明确的递归结束条件, 当满足了这个条件的时候就不再递归了。 下面用Java实现两个基础的递归算法/** * 求1+2+3+...+n的和 */ class ...
  • 算法-动态规划 Dynamic Programming--从菜鸟到老鸟

    万次阅读 多人点赞 2017-07-15 22:58:29
    前言最近在牛客网上做了几套公司的真题,发现有关动态规划(Dynamic Programming)算法的题目很多。相对于我来说,算法里面遇到的问题里面感觉最难的也就是动态规划(Dynamic Programming)算法了,于是花了好长时间...
  • 【算法导论】贪心算法,递归算法动态规划算法总结 一般实际生活中我们遇到的算法分为四类: 一>判定性问题 二>最优化问题 三>构造性问题 四>计算性问题 而今天所要总结的算法就是着重解决 最...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 461,443
精华内容 184,577
关键字:

动态规划递归算法