报名参加CloudWeGo黑客松,奖金直推双丰收! 了解详情
写点什么

理解递归与动态规划

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

评论

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

最新进展!Intel 18A产品,成功点亮!

E科讯

将数据库系统实践转向 AI:使用生成式 AI 创建高效的开发和维护实践

哦豁完蛋了

AI Codec

2024 年 7 月区块链游戏研报:市场波动与数据分化的挑战与机遇

Footprint Analytics

链游

官宣|Apache Flink 1.20 发布公告

Apache Flink

flink 实时计算 官宣

Prometheus Exporter 在观测云中的应用与优势

可观测技术

#Prometheus

在国内怎么运营TikTok?试试云手机!

Ogcloud

云手机 海外云手机 tiktok云手机 云手机海外版 海外云手机推荐

高并发场景下的库存管理,理论与实战能否兼得?

京东科技开发者

逻辑数据平台,多源异构实时数据高效同步的新途径

Aloudata

Data Fabric 数据编织 逻辑数据平台

NFTScan 正式上线 Gravity NFTScan 浏览器和 NFT API 数据服务

NFT Research

NFT NFTScan

润开鸿“龙芯+OpenHarmony”开发平台DAYU431先锋派新品发布

坚果

OpenHarmony 润开鸿

腾讯云大数据 TBDS 参编信通院《数据库发展研究报告》,引领数据湖仓创新

腾讯云大数据

TBDS

观测云:多云架构下的监控革新与效能提升

可观测技术

监控 多云

最佳实践:解读GaussDB(DWS) 统计信息自动收集方案

华为云开发者联盟

大数据 GaussDB(DWS) 企业号 8 月 PK 榜 2024企业号8月pk 实时查询

碳视野|加快构建碳排放双控制度体系工作方案

AMT企源

数字化转型 碳中和 双碳 碳管理 碳核算

企业业务前端监控实践

京东科技开发者

解锁亚马逊商品数据:API获取商品列表信息

tbapi

亚马逊API 亚马逊商品数据采集 亚马逊商品列表接口

ChatGPT 人工智能助理 Assistant

霍格沃兹测试开发学社

言犀智能体平台上线了!赶紧来试试!连接大模型与企业应用的“最后一公里”

京东科技开发者

Supersonic 发行逻辑:从原型到爆款,健康增长循环助力开发者走向成功

极客天地

安全性和合规性:保障企业数据的安全

可观测技术

数据安全 数据合规

继“蓝屏”事件之后,微软再次出现全球性宕机

我再BUG界嘎嘎乱杀

黑客 网络安全 安全 DDoS 网安

SRE是新一代ITIL的革新者

雅菲奥朗

SRE ITIL SRE培训 SRE考试 SRE认证

低代码与软件定制开发的完美结合:生产管理软件的高效解决方案

天津汇柏科技有限公司

低代码 软件定制开发 生产管理软件

IoTDB组件AI Node发布9个月,如何使用你了解了吗?

Apache IoTDB

观测云:零售业数据监控与分析的革新者

可观测技术

监控 零售

Grafana 与观测云:无缝集成的监控可视化体验

可观测技术

数据可视化

从困境到突破,EasyMR 集群迁移助力大数据底座信创国产化

袋鼠云数栈

集群架构 大数据存储 大数据计算与存储 大数据计算引擎 集群迁移

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