上海 网站备案,自媒体新手入门,环保网站可以做哪些内容,做淘宝客网站教程题目链接#xff1a;变态跳台阶 文章目录1 题目描述2 题目分析3 代码3.1 动态规划算法3.11 Java代码3.12 C代码3.2 递归算法3.21 Java代码3.22 C代码3.3 直接求解 公式#xff1a;f(n)2^(n-1)^3.31 Java代码3.32 C代码4 总结1 题目描述
一只青蛙一次可以跳上1级台阶#xf…题目链接变态跳台阶 文章目录1 题目描述2 题目分析3 代码3.1 动态规划算法3.11 Java代码3.12 C代码3.2 递归算法3.21 Java代码3.22 C代码3.3 直接求解 公式f(n)2^(n-1)^3.31 Java代码3.32 C代码4 总结 1 题目描述
一只青蛙一次可以跳上1级台阶也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
2 题目分析
假设f(n)代表青蛙跳上n级台阶的方法数。那么由于一次可以跳1级也可以跳2级…它也可以跳n级。所以f(n)f(n-1)f(n-2)…f(1)f(0);其中f(0)1根据这个式子可以写动态规划的算法
由上述公式知道
f(n)f(n-1)f(n-2)...f(1)f(0)
f(n-1)f(n-2)f(n-3)...f(1)f(0)将第二个式子合并到第一个式子得到
f(n)2*f(n-1); 根据这个式子可以写递归算法
又由上式知道
f(n)2*f(n-1)
f(n-1)2*f(n-2)
.
.
.
f(2)2*f(1)得出
f(n)2n-1 根据这个式子可以直接求解。
下面我们就以上述三种方法写代码
3 代码
3.1 动态规划算法
3.11 Java代码
public class Solution {public int JumpFloorII(int target) {//动态规划// 不使用公式求解采用动态规划if(target2)return target;int[] retnew int[target1];ret[0]1;ret[1]1;ret[2]2;int i,j,tmp0;for(i3;itarget;i){for(j0;ji;j){tmpret[j];} ret[i]tmp;tmp0;}return ret[target];}
}3.12 C代码
class Solution {
public:int jumpFloorII(int number) {// 不使用公式求解采用动态规划if(number0)return 0;int ret[number1];ret[0]1;ret[1]1;ret[2]2;int i,j,tmp0;for(i3;inumber;i){for(j0;ji;j){tmpret[j];} ret[i]tmp;tmp0;}return ret[number];}
};3.2 递归算法
3.21 Java代码
public class Solution {public int JumpFloorII(int target) {//采用递归求解 f(n)2*f(n-1);if(target0)return 0;if(target1)return 1;return 2*JumpFloorII(target-1);}
}3.22 C代码
class Solution {
public:int jumpFloorII(int number){//采用递归求解 f(n)2*f(n-1);if(number0)return 0;if(number1)return 1;return 2*jumpFloorII(number-1);}
};3.3 直接求解 公式f(n)2(n-1)
3.31 Java代码
public class Solution {public int JumpFloorII(int target) {//采用公式求解 f(n)2^(n-1)if(target0)return 0;//return (int)pow(2,number-1); 直接返回这一句不要下面的代码也可以int ret1;int i;for(i1;itarget;i)ret*2;return ret;}
}3.32 C代码
class Solution {
public:int jumpFloorII(int number) {//采用公式求解 f(n)2^(n-1)if(number0)return 0;//return (int)pow(2,number-1);int ret1;int i;for(i1;inumber;i)ret*2;return ret;}
};4 总结
理解上述公式的推导过程
探讨学习加 个人qq1126137994 个人微信liu1126137994
