AICon 上海站|90%日程已就绪,解锁Al未来! 了解详情
写点什么

理解递归与动态规划

  • 2020-01-15
  • 本文字数:2530 字

    阅读完需:约 8 分钟

理解递归与动态规划

1、从 Fibonacci 函数的四种实现聊起。

Fibonacci 数列,中文也译作斐波那契数列,相信大多数同学不会陌生,就是经典的兔子问题,以下图片内容来源于网络。



很清晰地,如上所述,如果把自然数到 Fibonacci 数列的映射看作一个函数 U(n)的话,那么有 U(n) = U(n-1) + U(n-2)。编码实现的话,自然是首选递归,Fibonacci 数列的递归实现如下:


Fibonacci数列实现方法1-------递归unsigned int Fibonacci_1(unsigned int n) {        if ((n == 1) || (n == 2)) {               return 1;        }          return Fibonacci_1(n - 1) + Fibonacci_1(n - 2); }
复制代码


看上去非常地简洁,非常地清晰,但是,有没有什么问题?有!而且是大问题,算法复杂度太高了,很容易发现算法复杂度为 O(2^n)。展开来看,大概就是这么个情况。



有没有办法可以优化一下呢?很容易发现,采用上述递归实现算法复杂度之所以高的原因就在于做了太多的重复计算。



到这里我们就要质疑一下,多问一句“有这个必要么?!”


当然没有!保存一下运算结果,以空间来换时间不可以么?来,试试看。


Fibonacci 数列实现方法 2-------递归+去重复计算


unsigned int Fibonacci_2(unsigned int n) {        static unsigned int f[100] = {0};               if ((n == 1) || (n == 2)) {               return 1;        }        else if (0 != f[n]) {               return f[n];        }          f[n] = Fibonacci_2(n - 1) + Fibonacci_2(n - 2);        return f[n]; }
复制代码


看上去似乎要好一点了,但是性能如何呢?来来来,是骡子是马拉出来 66,跑起来才知道。定义测试函数。


void testF(void) {        long t1, t2;        unsigned int fn;          t1 = clock();        fn = Fibonacci_1(40);        t2 = clock();          if (t1 <= t2) {               printf("Fibonacci_1 run time =%u, result = %u \n", t2 - t1, fn);        }          t1 = clock();        fn = Fibonacci_2(40);        t2 = clock();          if (t1 <= t2) {               printf("Fibonacci_2 run time =%u, result = %u \n", t2 - t1, fn);        } }
复制代码


实测结果



没有对比就没有伤害。


来,继续思考,是否还可以继续优化?实现方法 2 是以空间换时间,空间复杂度为 O(n),时间复杂度,因对每个 i<n,f(i)都只需要计算 1 次,因此时间复杂度也为 O(n)。目测,时间复杂度基本上已无优化空间,那么空间复杂度呢?静态数组 f 是否必要?



回过头来再看递归关系:U(n) = U(n-1) + U(n-2),也就是说只要依次算出 U(i),1<=i<n,就自然可以得到 U(n),并且计算 U(n)时,只需要知道 U(n-1)和 U(n-2)的值就可以。而对于 U(i),i<n-2 的值都用不到,保存这些东西干啥呢?由此出发,我们推演出代码实现方案 3


Fibonacci 数列实现方法 3-------正向计算


看上去貌似好简单的样子,没有递归,没有对中间结果的保存,so easy!


再对比一下性能来看看:


就是这么漂亮!


BTW:顺便提一句,事实上对于 Fibonacci 数列,是有通项公项可以直接计算的,这是高中奥数的基本功。


根据递推关系得特征根方程è X^2-X-1 = 0


解特征根方程得特征根è x1 = (1+5^(1/2))/2 x2 = (1-5^(1/2))/2


代入通项公式 F(n) = C1*(x1)^n + C2*(x2)^n,F(1)=1,F(2)=1,解得


è C1=1/(5)^(1/2) C2= -1/(5)^(1/2),得通项公式


èF(n) = ,非本文重点介绍内容,故在此不作过多介绍,如有兴趣,可以私聊。


补充编码实现:


Fibonacci 数列实现方法 4------不动点通项公式


unsigned int Fibonacci_4(unsigned int n) {        double sqrt5 = sqrt(5);        double root1 = (1 + sqrt5) / 2;        double root2 = (1 - sqrt5) / 2;               return (pow(root1, n) - pow(root2, n)) / sqrt5; }
复制代码


注: 实现方法 4,涉及开方,幂,以及除法等数学运算,受限于计算机精度限制,在 n 较大时,计算数值不准确,故不推荐。此外,仅为理论说明。

2、动态规划与递归的关系。

回过头来继续再看,Fibonacci 数列实现方法 2 和 Fibonacci 数列实现方法 3 到底有什么差别,本质上来讲,没有差别。这是由 Fibonacci 数列的递推关系式决定的。实现方法 3 之所以空间复杂度低,那仅是由于 Fibonacci 的递推关系实在是太简单了,F(n)仅依赖于 F(n-1)和 F(n-2),如果递推关系再复杂一些,甚至依赖项的个数再与 n 相关,两者就更像了。


但是从实现设计的思想上来看,两者略有不同。


实现方案 3 是正向的来考虑,换种写法,就是标准的动态规划。


但是这种考虑方式略显得反人类。为什么这样说呢?作为技术面试官,我在面试时,喜欢出一些算法方面的问题,来考察应聘者对基本数据结构和算法的理解,对于 Fibonacci 数列,大多数应聘者,包括能力很强的程序员,都是按照递归来写的(问题是很少有考虑性能因素的,都采用的实现方案 1),很少有人会用实现方案 3,不太符合我们的思维模式。


实现方案 2 相对实现方案 3 要更符合我们的思维模式,递归嘛,只要注意到了递归的性能问题,就自然水道渠成了。如刚才提到的实现方案 2 本质上来讲也是动态规划,或者说跟动态规划没有差别,只要有递推关系存在,本质上就是一样的。动态规划相对于递归,仅仅是减少了些不必要的重复计算而已。递归当然也可以做得到。而且更附合我们的思维模式。


所以,总结一下,涉及递推送关系的算法问题,可以用动态规划思维解决的,用递归一样可以解决,关键在于要注意到算法性能,通过矩阵数组保存中间过程运算结果,从而避免不必要的重复计算。一句话,去除了重复计算的递归就是动态规划。

3、实战演练。

题目描述


给定一个正整数,我们可以定义出下面的公式:


N=a[1]+a[2]+a[3]+…+a[m];


a[i]>0,1<=m<=N;


对于一个正整数,求解满足上面公式的所有算式组合,如,对于整数 4 :


4 = 4;


4 = 3 + 1;


4 = 2 + 2;


4 = 2 + 1 + 1;


4 = 1 + 1 + 1 + 1;


所以上面的结果是 5 。


注意:对于 “4 = 3 + 1” 和 “4 = 1 + 3” ,这两处算式实际上是同一个组合!


解答要求时间限制:1000ms, 内存限制:64MB


输入


每个用例中,会有多行输入,每行输入一个正整数,表示要求解的正整数 N(1 ≤ N ≤ 120) 。


输出


对输入中的每个整数求解答案,并输出一行(回车换行);


样例


输入样例 1 复制


4


10


20


输出样例 1


5


42


627


本文转载自华为云开发者社区。


2020-01-15 15:351385

评论

发布
暂无评论
发现更多内容

13.5大数据分析与可视化

张荣召

13.1大数据计算引擎Spark(上)

张荣召

年轻人不讲武德,乱用索引,你到底走了多少弯路?

比伯

Java 编程 架构 面试 程序人生

13.10作业

张荣召

13.8推荐引擎算法

张荣召

13.7分类聚类算法

张荣召

13.3流处理计算:Flink,Storm,Spark Streaming

张荣召

详解Spring5+SpringMVC5+MyBatis3.X,同时整合Redis缓存+ActiveMQ+项目等

Java架构追梦

Java spring 架构 mybatis springmvc

关于代码重构的灵魂三问:是什么?为什么?怎么做?

华为云开发者联盟

重构 代码 代码重构

Vmware+Centos设置静态IP

千泷

13.6网页排名算法PageRank

张荣召

如果云是水滴,Kubernetes就是水滴管理平台

华为云开发者联盟

云计算 管理 k8s

13.2大数据计算引擎Spark(下)

张荣召

AlibabaP8架构师整理,283页的Java核心资料pdf文档,学会后月薪4W没问题

Java架构之路

Java 程序员 架构 面试 编程语言

盘点2020 | 2020年读过的这些书

xcbeyond

读书感悟 盘点2020 七日更

未来30年推动全球经济增长的主要动力是数据资产

CECBC

区块链 移动互联网

优化PostgreSQL Autovacuum

PostgreSQLChina

数据库 postgresql 开源 优化

盘点2020 | 大龄程序员的进化(从自由职业者到讲师)

王磊

盘点2020

2020年度综合大盘点:火爆IT业的7大Java技术,每一项都是大写的“牛逼”!

Java 编程 微服务

13.4大数据基准测试工具HiBench

张荣召

公安大数据:警务大数据分析系统解决方案

t13823115967

智慧公安

全面到哭!阿里内部疯传Netty实战文档程序员必须人手一份

比伯

Java 编程 架构 程序人生 编程语言

淘宝|蚂蚁|菜鸟|盒马|滴滴|饿了么面经,已拿多个offer(Java岗)

Java架构之路

Java 程序员 架构 面试 编程语言

BATJ真题突击:Java基础+JVM+分布式高并发+网络编程+Linux

Java架构之路

Java 程序员 架构 面试 编程语言

Spark的分布式存储系统BlockManager全解析

华为云开发者联盟

spark 分布式 存储

13.9机器学习与神经网络

张荣召

安防小区管控系统建设,智慧社区智能化集成方案

t13823115967

智慧平安社区平台建设

天天CRUD,被领导怼,我是如何从小公司菜鸡到阿里P8架构师?,首次分享Java程序员黄金五年进阶心得

Java架构之路

Java 程序员 架构 面试 编程语言

iOS面试基础知识 (三)

iOSer

ios 面试 ios开发

敏捷规划,让你做一个有计划的开发人

华为云开发者联盟

敏捷 开发 规划

Alibaba技术专家必知必会的Java技术知识点,掌握这些理论+实践+技术是你通往阿里的路

Java架构之路

Java 程序员 架构 面试 编程语言

理解递归与动态规划_语言 & 开发_华为云开发者联盟_InfoQ精选文章