剑指offer-4：变态条楼梯
2024-10-07 06:31:37
##四、变态条楼梯
###题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
###分析
也是斐波那契数列问题，根据上述的思路，可以得到
f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(0),由此就有两种思路解答
(1)接着上式推出=> f(n)=2f(n-1)
(2)通过创建一个数组，进行循环，把f(0)、f(1)、...、f(n-1)的值存入数组中，然后把数组元素的值都相加得到f(n)
###代码
(1)
public class Solution {
public int JumpFloorII(int target) {
if(target==0){
return 0;
}
if(target==1){
return 1;
}
return 2*JumpFloorII(target-1);
}
}
(2)
public class Solution {
public int JumpFloorII(int target) {
if(target <= 2){
return target;
}
int[] dp = new int[target + 1]; // 0 号不使用
dp[1] = 1; //跟普通的 pre2 一个意思
dp[2] = 2; //跟普通的 pre1 一个意思
for (int i = 3; i <= target; i++){
for (int j = i - 1; j >= 1; j--){
dp[i] += dp[j];
}
dp[i]++;
}
return dp[target];
}
}
最新文章
- 易语言调用windows消息函数
- request.getHeader所想到的
- iOS开发 百度坐标点的计算
- github命令
- 配置NTP时间服务器
- <php>统计整个文件夹的大小
- perl 爬取同花顺数据
- C语言cgi(1)
- lambda表达式Expression<Func<Person, bool>> 、Func<Person, bool>区别
- unity3D加密如何做到防编译？
- 高级软件工程第四次作业（C++）
- linux基础-系统安装教程篇（centos6.5）
- 发现环 （拓扑或dfs）
- ranch流程处理图
- mysql案例-sysbench安装测试
- 使用redis镜像
- 【c++基础】accumulate
- IOS下 input 被软键盘方案遮盖问题解决
- IT项目经理岗位职责（转）
- poj 1692(动态规划)