剑指 Offer 10- II. 青蛙跳台阶问题
2023-02-18 16:34:59 时间
剑指 Offer 10- II. 青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例 1:
输入:n = 2
输出:2
示例 2:
输入:n = 7
输出:21
示例 3:
输入:n = 0
输出:1
解题思路
青蛙跳台阶问题,可以把n级台阶看成是n的函数,记为f(n),假设跳上n级台阶,有f(n)种跳法,则当n=0或者n=1时,返回1。
青蛙的最后一步只有两种情况: 跳上1级或2级台阶
- 当为1级台阶: 剩n-1个台阶,此情况共有f(n-1)种跳法;
- 当为2级台阶: 剩n-2个台阶,此情况共有f(n-2)种跳法。
因此n级台阶的不同跳法数目就成为f(n)=f(n-1)+f(n-2)
斐波那契数列问题:f(0)=0 f(1)=1 f(2)=1
青蛙跳台阶问题:f(0)=1 f(1)=1 f(2)=2
本题可转化为 求斐波那契数列第n项的值 ,斐波那契数列的定义是 f(n+1)=f(n)+f(n-1),生成第n项的做法有以下两种:
- 递归法:把f(n)问题的计算拆分成f(n-1)和f(n-2)两个子问题的计算,并递归,以f(0)和f(1)为终止条件,即n=0或者n=1时,返回1
- 动态规划:以斐波那契数列性质f(n+1)=f(n)+f(n-1)为转移方程,初始化前两个数字f(0)=1和f(1)=1,然后利用斐波那数列返回f(n),即斐波那契数列的第n个数字
代码:
class Solution {
public:
int numWays(int n) {
int a=1,b=1,sum;
for (int i = 0; i < n; i++)
{
sum=(a+b)%1000000007;
a=b;
b=sum;
}
}
};
class Solution {
public:
int numWays(int n) {
if(n==0) return 1;
if(n==1) return 1;
return numWays(n-1)+numWays(n-2);
}
};
相关文章
- 一个程序员的产品路:在线客服系统,开发两年的目标产品
- [CSS] media query媒体查询中的min-width和max-width
- [日常] robots.txt允许所有搜索引擎收录
- [nginx] 开启nginx反向代理的同时try_files指令排除静态资源请求到后端服务
- 在线客服系统源码|在线客服系统源码下载
- [日常] win10系统设置电脑从不休眠睡眠
- [前端] 项目中的ICONO 纯 CSS 绘制的一套图标库
- [微信公众号开发] 创建菜单测试的时候出现错误码40016
- [nginx] nginx判断文件存在直接返回,不存在的时候才执行反向代理
- [前端] ElementUI 中table表格数据解析渲染html格式
- [Nginx] root和alias指令的区别
- [TCP] write: broken pipe 的 原因
- [微信开发] 微信公众号被关注后如何回复多条消息?
- 客服在线咨询工具|即时聊天客服系统下载安装(包含APP)
- [微信开发] 解决:该公众号提供的服务出现故障,请稍后再试
- [日常] 华为手机截屏快捷键
- [windows] win10下的SysMain服务
- [nginx] X-Cache: HIT的意思
- [MySQL] 解决ERROR 1273 (HY000) at line 199: Unknown collation: 'utf8mb4_0900_ai_ci'
- [css] 加载本地文件出现跨域Cross origin requests are only supported for protocol schemes: http, data, chrome, chrome-extension, chrome-untrusted, https.