(原)剑指offer跳台阶和矩形覆盖
2024-08-23 09:31:16
跳台阶
- 时间限制:1秒空间限制:32768K
题目描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析同样为斐波那契数列边形这样的题肯定有公式
设n级台阶,总跳法 jumps
n jumps
1 1
2 2
3 3
4 5
5 8
猜测 fbonicc(n) = fbonicc(n-1) + fbonicc(n-2)
3 4 5
111 1111 1111(1)
21 211 211(1)
12 121 121(1)
112 112(1)
22 22(1)
111(2)
21(2)
12(2)
现在我们可以这样理解当 f(n) 比 f(n-1)少一个台阶
这一个台阶我们可以当一步跳完,也可以与前面的一步结合成一次跳两阶,So
前一种情况我们可以直接把这一步添到f(n-1)所有跳数后面,后一种情况很显然我们要向f(n - 1)借一步,也就是f(n-2)
所以得f(n) = f(n-1) + f(n-2)
c++代码实现
class Solution {
public:
int jumpFloor(int number) {
long long fiboncciA = 1;
long long fiboncciB = 2;
if (number == 1){
return fiboncciA;
}
if (number == 2) {
return fiboncciB;
} int i;
for (i = 3; i <= number; i++){
int tmp = fiboncciB;
fiboncciB = fiboncciA + fiboncciB;
fiboncciA = tmp;
}
return fiboncciB;
}
};
下一题
- 时间限制:1秒空间限制:32768K
- 题目描述
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
!!猛一看这道题有点没看懂
先来仔细分析一下
1:所有小矩形都竖着覆盖
2:当矩形横着覆盖时都是成对出现的
看到这里有感觉很熟悉,这不就是跳台阶问题吗?答案:是的
我们可以把题目改一下:有n个小矩形,去覆盖大矩形你可以一次用一个,也可以一次用两个,总共有多少种覆盖方法。
现在可以看懂了吧!
c++代码实现
代码同上
最新文章
- WIN7下查看CPU核心数
- Codeforces Round 319 # div.1 &; 2 解题报告
- Delphi连接Oracle控件ODAC的安装及使用(轉載)
- Android基础之项目结构分析
- 把centos 网卡接口eth2改成eth0
- 使用HashMap对象传递url參数有用工具类
- RSA 公私钥 互换问题
- 关于redis的主从、哨兵、集群
- 干货:教你如何监控 Java 线程池运行状态
- loadrunner controller如何执行测试
- leetcode 中等题(1)
- Effective MySQL之SQL语句最优化——读书笔记之二
- SoapUI使用笔记备忘
- 【uoj122】 NOI2013—树的计数
- 一、微信小游戏开发 --- 初次在微信开发者工具里跑Egret小游戏项目
- Apache Hadoop YARN – ResourceManager--转载
- Zookeeper(二) zookeeper集群搭建 与使用
- BZOJ5288 &; 洛谷4436 &; LOJ2508:[HNOI/AHOI2018]游戏——题解
- Python3 文件读写r,w,a
- leetcode88 Merged Sorted Array