从品牌网站建设到网络营销策划,从策略到执行的一站式服务
JZ71跳台阶扩展问题
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
数据范围:1 \le n \le 201≤n≤20
进阶:空间复杂度 O(1)O(1) , 时间复杂度 O(1)O(1)
对于最后一级台阶,我们可以由倒数第二级台阶跳1步,也可以由倒数第三级太极跳两步,即f(n)=f(n−1)+f(n−2)+...+f(n−(n−1))+f(n−n)=f(0)+f(1)+f(2)+...+f(n−1)f(n)=f(n-1)+f(n-2)+...+f(n-(n-1))+f(n-n)=f(0)+f(1)+f(2)+...+f(n-1)f(n)=f(n−1)+f(n−2)+...+f(n−(n−1))+f(n−n)=f(0)+f(1)+f(2)+...+f(n−1),因为f(n−1)=f(n−2)+f(n−3)+...+f((n−1)−(n−2))+f((n−1)−(n−1))f(n-1)=f(n-2)+f(n-3)+...+f((n-1)-(n-2))+f((n-1)-(n-1))f(n−1)=f(n−2)+f(n−3)+...+f((n−1)−(n−2))+f((n−1)−(n−1)),经整理得f(n)=f(n−1)+f(n−1)=2∗f(n−1)f(n)=f(n-1)+f(n-1)=2*f(n-1)f(n)=f(n−1)+f(n−1)=2∗f(n−1),因此每级台阶方案数是前面一级台阶方案数的2倍。
int[] bp = new int[target + 1];
bp[0] = 1;
bp[1] = 1;
for (int i = 2; i <= target; i++) {
bp[i] = 2 * bp[i - 1];
}
return bp[target];
package esay.JZ71跳台阶扩展问题;
public class Solution {
public int jumpFloorII(int target) {
//方法1:动态规划
/*int[] bp = new int[target + 1];
bp[0] = 1;
bp[1] = 1;
for (int i = 2; i <= target; i++) {
bp[i] = 2 * bp[i - 1];
}
return bp[target];*/
//方法2:递归
if (target <= 1) return 1;
return 2 * jumpFloorII(target - 1);
}
}
成都网站建设公司地址:成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220
成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.
专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网! | 成都网站建设哪家好? | 网站建设地图