AI实践哪家强?来 AICon, 解锁技术前沿,探寻产业新机! 了解详情
写点什么

理解递归与动态规划

  • 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:351488

评论

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

阿里数据中台底座的12年建设实践

阿里云大数据AI技术

我学编程时最后悔的事!

程序员鱼皮

Java c++ Python 大前端 后端

线上教育培训机构如何推广自己

石头IT视角

58字节常量池面试题,你如何应对?

卢卡多多

intern 字符串 7月日更

Linux之cal命令

入门小站

Linux

细节分析Linux中五种IO模型和三种实现方式

Linux服务器开发

网络编程 epoll Linux服务器开发 Linux后台开发 IO模型

【得物技术】得物开放平台进阶之路

得物技术

安全 后端 平台 订单

怎么才能写出100个用户体验的关键时刻?

石云升

读书笔记 用户体验 关键时刻 7月日更

实践解析丨如何通过 WebAssembly 在 Web 进行实时视频人像分割

声网

大前端 WebRTC webassembly

C# 三个Timer

喵叔

7月日更

百度AI寻人获评《新周刊》2021年度公益项目

百度大脑

人工智能 寻人

实战-使用 SSM 工具创建可动态扩容的存储池

学神来啦

Linux 运维 ssm Linux教程

6月热点:BML全新升级WebIDE编程环境,度目智能视频分析盒G1上新

百度大脑

人工智能 BML

启动、内存、卡顿三大分析,用户体验就用它?

App

《人这一辈子,都在为认知闭环买单》读后感---刘润

Changing Lin

药物研发使用北鲲云高性能计算平台,有效解决研发效率问题

北鲲云

上线仅7天,GitHub已标星48.4k!原来是阿里巴巴内部《高并发系统设计》

Java redis 编程 架构 面试

在线条码生成器

入门小站

工具

Ipfs国家认可吗?国家对ipfs区块链是什么政策?

区块链 分布式存储 IPFS fil

从零开始学习3D可视化之数据对接(3)

ThingJS数字孪生引擎

大前端 数据 物联网 可视化 数字孪生

可以同时管理公有云和私有云资源的软件哪个好?

行云管家

公有云 私有云 云管平台 云资源

Android Flutter 多实例实践

网易云信

flutter 架构

微观管理?

escray

学习 极客时间 朱赟的技术管理课 7月日更

结构化流-Structured Streaming(八-下)

Databri_AI

spark 流式计算框架 structuredStreaming

Apache Druid 简介

HoneyMoose

学习下服务器端漏洞,受益匪浅!

网络安全学海

运维 网络安全 信息安全 漏洞扫描 渗透测试·

极光开发者周刊【No.0723】

极光GPTBots-极光推送

网络攻防学习笔记 Day83

穿过生命散发芬芳

网络攻防 7月日更

模块三作业

燕燕 yen yen

架构训练营

【等保知识】等保测评机构申请条件,所需资料以及流程

行云管家

等保 堡垒机 行云管家 等保测评

使用数据库乐观锁的方式解决数值累加的问题

陈靓-哲露

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