产品战略专家梁宁确认出席AICon北京站,分享AI时代下的商业逻辑与产品需求 了解详情
写点什么

理解递归与动态规划

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

评论

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

28天瞎写的第二百三十一天:一次被骗的故事

树上

28天写作

谁能拯救终将凋落的头发「幻想短篇 21/28」

道伟

28天写作

折腾CUDA环境,搭建TF2开发环境

IT蜗壳-Tango

七日更

批判性思维自修课(三)

石君

28天写作 批判性思维

创始人去世,股权怎么办?|视频号28天(21)

赵新龙

28天写作

凝聚人心并不难,小诀窍让团队跟你一条心

一笑

管理 激励 28天写作

网站自动化任务脚本

Kylin

七日更

低代码:Microsoft Power Platform

lidaobing

低代码 28天写作 Power Platform

阿里巴巴管理三板斧

Ian哥

28天写作

【JS】预编译

德育处主任

JavaScript 大前端 js 28天写作

冲突域和广播域区别,集线器、交换机和路由器对比

创业失败启示录|老老王上的人生第一课

阿萌

28天写作 创业失败启示录 青城

大数据知识专栏 - MapReduce 的自定义分组求TopN

小马哥

大数据 hadoop mapreduce 七日更

西少爷肉夹馍的股权纠纷 | 视频号28天(22)

赵新龙

28天写作

大数据丨ClickHouse在京东能源管理平台的实践

京东科技开发者

数据库 大数据

LeetCode题解:200. 岛屿数量,DFS,JavaScript,详细注释

Lee Chen

算法 大前端 LeetCode

如何查看github评价

Albert

GitHub

机器学习·笔记之:Cost Function - Intuition II

Nydia

个人隐私后续

张老蔫

28天写作

碎碎念之「程序员的时间都花在了哪?」

Justin

设计原则 代码规范 28天写作 技术债

企业级低代码平台的选型和建设思考

李小腾

Serverless Kubernetes:理想,现实与未来

阿里巴巴云原生

Serverless 容器 运维 云原生 k8s

扎根CNCF社区贡献五年是怎样的体验?听听华为云原生开源团队的负责人怎么说

华为云开发者联盟

容器 Volcano cncf kubeedge 代码开发

对机器视觉领域的几点看法

JiangX

机器视觉 28天写作

我的算法学习之路

熊斌

学习方法 算法 28天写作

“大禹针”在北江大堤上线,浪潮助力广东水利新基建落地

新基建

LiteOS调测利器:backtrace函数原理知多少

华为云开发者联盟

架构 内存 函数 LiteOS backtrace

Java 创建线程有哪些方式

武哥聊编程

Java 多线程 28天写作

HTTPS实现原理

架构精进之路

https 七日更 28天写作

云算力挖矿系统开发app,矿机租赁交易平台搭建

v16629866266

微服务转型系列1:农商行数字化转型的烦恼

BoCloud博云

微服务 银行数字化转型 API 服务治理

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