JZ71跳台阶扩展问题

描述

一只青蛙一次可以跳上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); } }