递归与动态规划---基础篇1

ps:最近几天正在刷一些有关动态规划的题,我会把自己学习时的想法以及做题的想法记录下来。(小白第一次写作,希望大家多多支持)

题目1:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法

对于这道题,我第一眼看到的想法是用递归的做法的,用递归的方法做题,我觉得最重要的就是找出 这个函数与下一个函数之间的关系 以及 一个函数体结束的临界条件(即递归的结束)。

例如就本题而言,

1.第一步先找这个函数与下一个函数之间的关系:

假如有n个台阶,跳上一个n级的台阶的跳法总数为f(n).

我们在跳的过程中,每一次有两种跳法,即跳一个或两个台阶。

第一种跳法:第一次我跳了一个台阶,那么还剩下n-1个台阶还没跳,剩下的n-1个台阶的跳法有f(n-1)种。

或者用

第二种跳法:第一次跳了两个台阶,那么还剩下n-2个台阶还没,剩下的n-2个台阶的跳法有f(n-2)种。

由此不难得出递归公式:f(n) = (n-1) + f(n-2);

2.第二步,找出递归的结束条件

当n <= 0时,跳法为0,即此时f(n) = 0

当只剩下一个台阶n = 1时,那么只有一种跳法,即f(1) = 1;

当n = 2时,此时跳法为2种,即f(2) = 2;

函数与函数之间的关系以及递归的临界条件都找出来了,那么接下来就可以开始写代码了。如下所示:

不过观察一下你就会发现,其实在递归的过程中,有很多相同的)f(n)重复算。

如下图:

算一下你就知道,时间复杂度是指数级别的。如果是比赛这样做的话,绝对超时不通过

因此对于那些重复算过的,其实我们可以不用在重复递归来算它的,也就是所我们可以把f(n)算的结果一边给保存起来,这种就是动态规划的思想。

也就是说,我们可以把每次计算的结果保存中一个map容器里,把n作为key,f(n)作为value.然后每次要递归的时候,先查看一下这个f(n)我们是否已经算过了,如果已经算过了,我们直接从map容器里取出来返回去就可以了。如下:

这种方法会快很多很多。

实际上,对于f(n) = f(n-1) + f(n - 2)这种有递推关系的题,其实和斐波那契数列很相似,还可以这样做:

问题2: 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。 求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析,其实这道题和上面那道题一样的,只是本来每次跳有两种选择,现在有n中选择,即f(n) = f(n-1) + f(n - 2) + f(n-3)+.....+f(1);

因此做法如下:

如果你有其他想法,或者更完美的做法,欢迎指点江山。

原文发布于微信公众号 - 苦逼的码农(di201805)

原文发表时间:2018-05-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏WD学习记录

Python数据结构与算法笔记(5)

邻接矩阵优点是简单,对于小图,很容易看到哪些节点连接到其他节点。但是大多数单元格是空的,即稀疏。

1313
来自专栏温安适的blog

最小生产树Prim和Kruskal

47512
来自专栏程序生活

Leetcode-Easy 70. Climbing Stairs

21. Merge Two Sorted Lists 描述: 有n阶楼梯,每步只能走1个或2个台阶,请问到达第n阶楼梯一共有多少走法? ? ...

3296
来自专栏小樱的经验随笔

邻接矩阵存储有向图(详解)

邻接矩阵存储有向图 【输入描述】   输入文件包含多组测试数据,每组测试数据描述了一个无权有向图。每组测试数据第一行为两个正整数n和m,1<=n<=100,1<...

2949
来自专栏数据结构与算法

2039 骑马修栅栏

题目描述 Description Farmer John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。 John是一个与其他农民一样懒的人...

38111
来自专栏恰童鞋骚年

数据结构基础温故-5.图(中):最小生成树算法

图的“多对多”特性使得图在结构设计和算法实现上较为困难,这时就需要根据具体应用将图转换为不同的树来简化问题的求解。

1522
来自专栏编程理解

数据结构(十二):最短路径(Dijkstra算法)

Dijkstra 算法使用贪心策略计算从起点到指定顶点的最短路径,通过不断选择距离起点最近的顶点,来逐渐扩大最短路径权值,直到覆盖图中所有顶点。

2912
来自专栏数据结构与算法

4768 跳石头

4768 跳石头 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 一年一度的“...

27710
来自专栏猿人谷

斐波那契额数列及青蛙跳台阶问题

题目:写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。  斐波那契(Fibonacci)数列定义如下: ? 效率很低的解法:...

2428
来自专栏用户画像

5.2 图的存储及基本操作

图的存储必须要完整、准确地反映顶点集和边集的信息。根据不同图的结构和算法,可以用不同的存储方式,但不同的存储方式将对程序的效率产生很大的影响,因此,所选的存储结...

1003

扫码关注云+社区

领取腾讯云代金券