每日算法之跳台阶扩展问题(跳台阶算法可以跳n级)

  本篇文章为你整理了每日算法之跳台阶扩展问题(跳台阶算法可以跳n级)的详细内容,包含有跳台阶问题升级版 跳台阶算法可以跳n级 跳台阶问题-----递归算法 跳台阶输出方案 每日算法之跳台阶扩展问题,希望能帮助你了解 每日算法之跳台阶扩展问题。

  

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

 

  数据范围:1 \le n \le 201≤n≤20

  进阶:空间复杂度 O(1)O(1) , 时间复杂度 O(1)O(1)

  

 

  方法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];

  

 

  方法2 递归

  

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);

  

 

  以上就是每日算法之跳台阶扩展问题(跳台阶算法可以跳n级)的详细内容,想要了解更多 每日算法之跳台阶扩展问题的内容,请持续关注盛行IT软件开发工作室。

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: