文档章节

递归和动态规划

LoSingSang
 LoSingSang
发布于 03/12 21:52
字数 1245
阅读 24
收藏 1

递归算法就是通过解决同一问题的一个或多个更小的实例来最终解决一个大问题的算法。为了在C语言中实现递归算法,常常使用递归函数,也就是说能调用自身的函数。递归程序的基本特征:它调用自身(参数的值更小),具有终止条件,可以直接计算其结果。

      在使用递归程序时,我们需要考虑编程环境必须能够保持一个其大小与递归深度成正比例的下推栈。对于大型问题,这个栈需要的空间可能妨碍我们使用递归的方法。

     一个递归模型为分治法,最本质的特征就是:把一个问题分解成独立的子问题。如果子问题并不独立,问题就会复杂的多,主要原因是即使是这种最简单算法的直接递归实现,也可能需要难以想象的时间,使用动态规划技术就可以避免这个缺陷。

     例如,斐波那契数列的递归实现如下:

    int F(int i)

    {

             if(i < 1)  return 0;

             if(i == 1) return 1;

              return F(i-1) + F(i - 2);

    }

    千万不要使用这样的程序,因为它的效率极低,需要指数级时间。相比之下,如果首先计算前N个斐波那契数,并把它们存储在一个数组中,就可以使用线性时间(与N成正比)计算F。

 

      F[0] = 0;F[1] = 1;

      for(i = 2; i <= N; i++)

            F[i] = F[i-1] + F[i-2];

     这个技术给了我们一个获取任何递归关系数值解的快速方法,在斐波那契数的例子中,我们甚至可以舍弃数组,只需要保存前两个值。

     由上面的讨论我们可以得出这样的结论:我们可以按照从最小开始的顺序计算所有函数值来求任何类似函数的值,在每一步使用先前已经计算出的值来计算当前值,我们称这项技术为自底向上的动态规划。只要有存储已经计算出的值的空间,就能把这项技术应用到任何递归计算中,就能把算法从指数级运行时间向线性运行时间改进。

    自顶向下的动态规划甚至是一个更简单的技术,这项技术允许我们执行函数的代价与自底向上的动态规划一样(或更小),但是它的计算是自动的。我们实现递归程序来存储它所计算的每一个值(正如它最末的步骤),并通过检查所存储的值,来避免重新计算它们的任何项(正如它最初的步骤)。这种方法有时也称作为备忘录法。

                       斐波那契数(动态规划)

通过把所计算的值存储在递归过程的外部数组中,明确地避免重复计算。这一程序计算的时间与N成正比。

                  int F(int i)

                  {

 

                          if(knownF[i] != unknown)

                                 return knownF[i];

                          if(i == 0) t = 0;

                          if(i == 1) t = 1;

                          if(i > 1)  t = F(i - 1) + F(i - 2);

                          return knownF[i] = t;

                  }

 

 

       性质:动态规划降低了递归函数的运行时间,也就是减少了计算所有小于或等于给定参数的递归调用所要求的时间,其中处理一次递归调用的时间为常量。

       我们不需要把递归参数限制到单整形参数的情况。当有一个带有多个整形参数的函数时,可以把较小子问题的解存储在多维数组中,一个参数对应数组的一维。其他那些完全不涉及整形参数的情形,就使用抽象的离散问题公式,它能让我们把问题分解为一个个的小问题。

      在自顶向下的动态规划中,我们存储已知的值;在自底向上的动态规划中,我们预先计算这些值。我们常常选择自顶向下的动态规划而不选自底向上动态规划,其原因如下:

     1 自顶向下的动态规划是一个自然的求解问题的机械转化。

     2 计算子问题的顺序能自己处理。

     3 我们可能不需要计算所有子问题的解。

     我们不能忽视至关重要的一点是,当我们需要的可能的函数值的数目太大以至于不能存储(自顶向下)或预先计算(自底向上)所有值时,动态规划就会变得低效。自顶向下动态规划确实是开发高效的递归算法实现的基本技术,这类算法应纳入任何从事算法设计与实现所需的工具箱。

本文转载自:http://blog.csdn.net/deepit/article/details/6530282

共有 人打赏支持
LoSingSang
粉丝 3
博文 32
码字总数 6976
作品 0
深圳
程序员
私信 提问
递归 (二)

原谅我好几天没写专栏,我去写放了两个月的 NOIP 题了…… 尾递归、非尾递归 首先,来两个概念:尾递归和非尾递归。 顾名思义,如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称...

BillAlen
2016/10/31
0
0
动态规划法(一)从斐波那契数列谈起

动态规划法与分治方法   动态规划(Dynamic Programming)与分治方法相似,都是通过组合子问题的解来求解原问题。不同的是,分治方法通常将问题划分为互不相交的子问题,递归地求解子问题,...

jclian91
05/28
0
0
LeetCode: Distinct Subsequence

问题描述: Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original stri......

ljie-PI
2013/12/23
0
0
Dynamic Programming(动态规划)

Introduction 作为科班出身的程序员,算法还是得懂一点点的。------佚名(我)。 动态规划是一个看起来很高大上的名字,让人一听就很想知道这到底是个啥,所以我常常需要跟身边好奇的朋友们解释...

Mark1996
06/23
0
0
分治法,动态规划及贪心算法感悟

分治法,动态规划法,贪心算法这三者之间有类似之处,比如都需要将问题划分为一个个子问题,然后通过解决这些子问题来解决最终问题。但其实这三者之间的区别还是蛮大的。 1.分治法 分治法(d...

努力的C
2017/10/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

学习心得《稻盛和夫经营学》的读后感2300字

学习心得《稻盛和夫经营学》的读后感2300字: 作者:张宪军;稻盛和夫信奉明朝王阳明的一句话:良知没处,万法难度。人们把它理解为管理者要有在纯正心态下要有好的做事方法,不然是很难成功...

原创小博客
18分钟前
0
0
红外接收器驱动开发

背景:使用系统的红外遥控软件没有反应,然后以为自己接线错误,反复测试,结果烧坏了一个红外接收器,信号主板没有问题。所以自己开发了一个红外接收器的python驱动。接线参见https://my.os...

mbzhong
40分钟前
2
0
ActiveMQ消息传送机制以及ACK机制详解

AcitveMQ是作为一种消息存储和分发组件,涉及到client与broker端数据交互的方方面面,它不仅要担保消息的存储安全性,还要提供额外的手段来确保消息的分发是可靠的。 一. ActiveMQ消息传送机...

watermelon11
今天
1
0
HashTable和Vector为什么逐渐被废弃

HashTable,不允许键值为null,还一个就是put方法使用sychronized方法进行线程同步,单线程无需同步,多线程可用concurren包的类型。 如编程思想里面说的作为工具类,封闭性做的不好没有一个...

noob_chr
昨天
1
0
Win10 下安装Win7双系统

很多人买了预装64位Win8/8.1的电脑后想重装(或者再安装一个)Win7系统,但是折腾半天发现以前的方法根本不奏效。这是因为预装Win8/8.1的电脑统一采用了UEFI+GPT引导模式,传统的BIOS(Legacy...

yaly
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部