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

71 阅读 0 评论 47 点赞

我是靠谱客的博主稳重秋天，这篇文章主要介绍剑指Offer:变态跳台阶Java/Python1.题目描述2.算法描述3.代码描述，现在分享给大家，希望可以做个参考。

1.题目描述

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

2.算法描述

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

3.代码描述

3.1.Java代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//方法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];
    }
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
//方法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
2
3
4
5
6
7
8
9
10
11
12
13
#方法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]

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
#方法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]