剑指Offer:变态跳台阶Java/Python1.题目描述2.算法描述3.代码描述

1.题目描述

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

2.算法描述

方法1：与上一题（跳台阶）类似，只不过现在当n>=2之后，你可以从0,1,…,k-1分别跳到第k级。所以递推关系变为如下：
$$f(n)=\{\begin{array}{ll}1& n=0,1\\ f(0)+f(1)+...+f(n-1)& n>=2\end{array}$$
方法2：既然在$n>=2$时，
$$f(n)=f(0)+f(1)+...+f(n-1)\text{\hspace{1em}(1)}$$
就是说,
$$f(n-1)=f(0)+f(1)+...+f(n-2)\text{\hspace{1em}(2)}$$
把$(2)$式代入$(1)$式可得$f(n)=2\ast f(n-1)$，所以可以更加简洁一些。时间复杂度一下从$O(n^2)$降到$O(n)$。

3.代码描述

3.1.Java代码

//方法1
public class Solution {
    public int JumpFloorII(int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<target+1;i++){
            for(int j=0;j<i;j++){
              dp[i] += dp[j];
            }
        }
        return dp[target];
    }
}

//方法2：
public class Solution {
    public int JumpFloorII(int target) {
    	int[] dp = new int[target+1];
    	dp[0] = 1;
    	dp[1] = 1;
    	for(int i=2;i<target+1;i++)
    	    dp[i] = 2 * dp[i-1];
    	return dp[target];
    }
}

3.2.Python代码

#方法1
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        dp = [0] * (number+1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2, number+1):
            for j in range(0,i):
                dp[i] += dp[j]
        return dp[number]

#方法2：
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        dp = [0] * (number+1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2, number+1):
            dp[i] = 2 * dp[i-1]
        return dp[number]

最后

以上就是稳重秋天最近收集整理的关于剑指Offer:变态跳台阶Java/Python1.题目描述2.算法描述3.代码描述的全部内容，更多相关剑指Offer:变态跳台阶Java/Python1内容请搜索靠谱客的其他文章。