正文

变态跳台阶(代码片段)

ustca  ustca  2023-04-18  407

关键词：

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

思路

斐波那契数列变种。

f(n)=f(n-1)+f(n-2)+……f(1)
f(n-1)=f(n-2)+……f(1)
两式相减得f(n)=2f(n-1)
时间复杂度O(n)，空间复杂度O(1)。
动态规划
f(n)=f(n-1)+f(n-2)+……f(1)
时间复杂度O(n2)，空间复杂度O(n)。

公式代码

public class Solution 
    public int JumpFloorII(int target) 
        if(target < 3)    return target;
        int ans = 2;
        for(int i = 2; i < target; i++) 
            ans *= 2;
        
        return ans;

dp代码

import java.util.Arrays;
public class Solution 
    public int JumpFloorII(int target) 
        int[] dp = new int[target+1];
        Arrays.fill(dp, 1);
        dp[0] = 0;
        for(int i = 2; i <= target; i++)
            for(int j = 1; j < i; j++) 
                dp[i] += dp[j];
            
        
        return dp[target];

笔记

动规算法用于理解一维的动态规划。

剑指offer---变态跳台阶(代码片段)

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。publicclassSolutionpublicintJumpFloorII(inttarget)if(target<=0)return0;if(target==1)return1;returnJumpFloorII(target-1... 查看详情

剑指offer09变态跳台阶(代码片段)

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。java版本：publicclassSolutionpublicstaticvoidmain(String[]args)longstartTime=System.currentTimeMillis();System.out.println("第4项的结果... 查看详情

剑指offer：变态跳台阶(代码片段)

目录题目解题思路具体代码题目题目链接剑指offer：变态跳台阶题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。解题思路这题的名字和题面都和跳台... 查看详情

跳台阶，变态跳台阶，矩阵覆盖(代码片段)

...self,number):#writecodeherea=1b=1foriinrange(number):a,b=b,a+breturna二、变态跳台阶1、问题描述变态跳台阶一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。2、代码classSolutio... 查看详情

剑指offer变态跳台阶(代码片段)

目录题目描述解法1实现代码解法2实现代码解法3实现代码题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。解法1本题是【剑指Offer】跳台阶的进化版... 查看详情

剑指offer-java-变态跳台阶(代码片段)

变态跳台阶题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。代码：packagecom.hlq.test;/***@authorhelongqiang*@date2020/5/1120:34*//***一只青蛙一次... 查看详情

跳台阶问题（递归动态规则变态跳台阶）(代码片段)

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。分析：青蛙每次只有一阶或者两阶两种跳法，那么：假设第一次跳的是一阶，那么剩下的n-1个台阶，跳法是f(n-1)假设第... 查看详情

c_cpp变态跳台阶的.cpp(代码片段)

查看详情

剑指offer——变态跳台阶(代码片段)

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。题解：classSolutionpublic:intjumpFloorII(intnumber)vector<int>dp(number+1,0);dp[0]=1;dp[1]=1;dp[2]=2;for(inti=3;i<=number;... 查看详情

剑指offer[9]——变态跳台阶(代码片段)

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。这个题目是跳台阶的进阶版，其实跟大家分析一下，这道题其实比上一道题简单。在这道题目中，... 查看详情

9.变态跳台阶(代码片段)

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。题目解答publicclassSolutionpublicintJumpFloorII(inttarget)if(target<=0)return-1;elseif(target==1)return1;elsereturn2*JumpFlo... 查看详情

剑指offer9.变态跳台阶(代码片段)

9.变态跳台阶题目一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思路与上题相似，假设要到3级，那么可以从0，1，2级直接到三级，那么f3=f1+f2+1，f2=f1+1，f3=... 查看详情

剑指offer变态跳台阶(代码片段)

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思路：做一个简单的数学推导，令跳上一个n级台阶总共的跳法为F(n)，F(n)=F(n-1)+F(n-2)+....+F(0)=F(n-1)+F(n-1)... 查看详情

变态跳台阶(代码片段)

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思路斐波那契数列变种。f(n)=f(n-1)+f(n-2)+……f(1)f(n-1)=f(n-2)+……f(1)两式相减得f(n)=2f(n-1)时间复杂度O(n... 查看详情

变态跳台阶

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思路：每个台阶都有跳与不跳两种情况（除了最后一个台阶），最后一个台阶必须跳。所以共... 查看详情

青蛙跳台阶衍生之变态跳台阶(递归，思路分析及代码实现)

//一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。//思路:接上一个跳台阶问题思路继续分析，上个问题中，青蛙只能跳1级或者2级。则最后一跳只... 查看详情

剑指offer变态跳台阶(代码片段)

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。代码：1//动态规划版2classSolution3public:4intjumpFloorII(intnumber)5if(number==0)6return0;7intcount=1;8for(inti=1;i&... 查看详情