【剑指Offer】9、变态跳台阶
2024-08-31 03:14:54
题目描述:
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解题思路:
当只有一级台阶时,f(1)=1;当有两级台阶时,f(2)=f(2-1)+f(2-2);一般情况下,当有n级台阶时,f(n)=f(n-1)+f(n-2)+···+f(n-n)=f(0)+f(1)+···+f(n-1),同理,f(n-1)=f(0)+f(1)+···+f(n-2).
因此,根据上述规律可以得到:f(n)=2*f(n-1)。这时一个递推公式,同样为了效率问题,用循环可以实现。
编程实现(Java):
public int JumpFloorII(int target) {
if(target<=0)
return 0;
if(target==1)
return 1;
int res=1;
for(int i=2;i<=target;i++)
res=2*res;
return res;
}
最新文章
- 在Autodesk Vault 2014中使用VDF(Vault Development Framework) API获取所有文件的属性信息
- three.js 显示一条线
- Perl语言——简单说明
- 【问题与思考】1+";1";=?
- nat123 与微信公众号开发者测试账号配合调试
- Android 关于网址,电话号码,邮箱的正则表达式-最权威
- myeclipse的class文件编译设置
- Java面经 面试经验 互联网公司面试经验 后端面试经验
- 编译器重复定义错误:error C2371: &#39;SIZE&#39; : redefinition; different basic types
- vue 在已有的购买列表中(数据库返回的数据)修改商品数量
- Node.js 网络
- CSS常见布局问题整理
- 使用CCS调试基于AM335X的SPL、Uboot(原创)
- centos 主机名突然变成bogon的解决方法
- 加速JDBC的快捷方法
- 几个简单易懂的排序算法php
- JavaEE笔记(十三)
- Spark Shuffle(三)Executor是如何fetch shuffle的数据文件(转载)
- js搜索算法——二分搜索
- 将Halcon导出的多个dxf文件合并成一个分图层的dxf文件
热门文章
- 一篇文章贯穿ACE各种发送接收组件 1.2版
- 【POJ 2983】Is the Information Reliable?(差分约束系统)
- Linux -- 内存控制之oom killer机制及代码分析
- WCF学习笔记——配置服务引用
- java.lang.IllegalStateException: Can not perform this action after onSaveInstanceState问题解决
- Android 的Recovery机制【转】
- 使用tortoisegit修改日志
- Android和H5交互-基础篇
- uoj#149
- 排序系列 之 归并排序算法 —— Java实现