漫画:什么是动态规划?

简介: 漫画:什么是动态规划?

微信图片_20220421112358.jpg微信图片_20220421112403.jpg微信图片_20220421112406.jpg微信图片_20220421112408.jpg微信图片_20220421112411.jpg微信图片_20220421112414.jpg微信图片_20220421112417.jpg

题目:


有一座高度是10级台阶的楼梯,从下往上走,每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。


比如,每次走1级台阶,一共走10步,这是其中一种走法。我们可以简写成 1,1,1,1,1,1,1,1,1,1。

微信图片_20220421112420.jpg

比如,每次走2级台阶,一共走5步,这是另一种走法。我们可以简写成 2,2,2,2,2。

微信图片_20220421112423.jpg

当然,除此之外,还有很多很多种走法。

微信图片_20220421112425.jpg微信图片_20220421112428.jpg微信图片_20220421112430.jpg微信图片_20220421112432.jpg微信图片_20220421112434.jpg微信图片_20220421112436.jpg微信图片_20220421112439.jpg微信图片_20220421112441.jpg微信图片_20220421112444.jpg微信图片_20220421112446.jpg微信图片_20220421112449.jpg微信图片_20220421112451.jpg微信图片_20220421112454.jpg

第一种情况:

微信图片_20220421112457.jpg


第二种情况:微信图片_20220421112459.jpg微信图片_20220421112501.jpg微信图片_20220421112504.jpg微信图片_20220421112507.jpg微信图片_20220421112513.jpg微信图片_20220421112515.jpg


把思路画出来,就是这样子:


微信图片_20220421112517.jpg微信图片_20220421112520.jpg微信图片_20220421112522.jpg微信图片_20220421112524.jpg微信图片_20220421112528.jpg微信图片_20220421112530.jpg


F(1) = 1;

F(2) = 2;

F(n) = F(n-1)+F(n-2)(n>=3)


微信图片_20220421112532.jpg微信图片_20220421112536.jpg微信图片_20220421112538.jpg微信图片_20220421112541.jpg微信图片_20220421112543.jpg微信图片_20220421112545.jpg微信图片_20220421112547.jpg

各位亲们,由于动态规划所涵盖的知识点比较多,这一题材讲分成三篇漫画来讲解,越往后越烧脑,也越有趣。

相关文章
|
算法 测试技术 C++
C++算法:美丽塔O(n)解法单调栈
C++算法:美丽塔O(n)解法单调栈
一段动态规划代码赏析
输入一个字符串 和 一个pattern. 返回结果是否匹配上
57 0
|
算法
《趣学算法-动态规划-0-1背包问题》阅读笔记
《趣学算法-动态规划-0-1背包问题》阅读笔记
151 0
《趣学算法-动态规划-0-1背包问题》阅读笔记
|
存储 算法
一文学懂动态规划
一文学懂动态规划
129 0
一文学懂动态规划
|
存储 算法
漫画:什么是动态规划?(整合版)
题目: 有一座高度是10级台阶的楼梯,从下往上走,每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。 比如,每次走1级台阶,一共走10步,这是其中一种走法。我们可以简写成 1,1,1,1,1,1,1,1,1,1。
137 0
漫画:什么是动态规划?(整合版)
|
存储 算法 测试技术
漫画:什么是最小生成树?
它的最小生成树是什么样子呢?下图绿色加粗的边可以把所有顶点连接起来,又保证了边的权值之和最小,去掉那些多余的边,该图的最小生成树如下。
122 0
漫画:什么是最小生成树?
|
算法 搜索推荐 Java
漫画:什么是桶排序?
让我们先来回顾一下计数排序: 计数排序需要根据原始数列的取值范围,创建一个统计数组,用来统计原始数列中每一个可能的整数值所出现的次数。
189 0
漫画:什么是桶排序?
|
算法 搜索推荐
漫画:什么是基数排序?
数组每一个下标位置的值,代表了数列中对应整数出现的次数。 有了这个“统计结果”,排序就很简单了。直接遍历数组,输出数组元素的下标值,元素的值是几,就输出几次: 0,1,1,2,3,3,3,4,4,5,5,6,7,7,8,9,9,9,9,10 显然,这个输出的数列已经是有序的了。 这就是计数排序的朴素版本。
161 0
漫画:什么是基数排序?
|
存储
漫画:什么是计数排序?
如何给无序的随机整数排序呢? 非常简单,让我们遍历这个无序的随机数列,每一个整数按照其值对号入座,对应数组下标的元素进行加1操作。 比如第一个整数是9,那么数组下标为9的元素加1
136 0
漫画:什么是计数排序?
|
存储
漫画:什么是 “锦标赛排序” ?
如图中所示,我们把原本的冠军选手5排除掉,在四分之一决赛和他同一组的选手6就自然获得了直接晋级。 接下来的半决赛,选手7打败选手6晋级;在总决赛,选手7打败选手3晋级,成为了新的冠军。 因此我们可以判断出,选手7是总体上的亚军。
186 0
漫画:什么是 “锦标赛排序” ?