1.题目描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
2.算法描述
方法1:与上一题(跳台阶)类似,只不过现在当n>=2之后,你可以从0,1,…,k-1分别跳到第k级。所以递推关系变为如下:
f
(
n
)
=
{
1
n
=
0
,
1
f
(
0
)
+
f
(
1
)
+
.
.
.
+
f
(
n
−
1
)
n
>
=
2
f(n)= begin{cases} 1 &{n=0,1}\ f(0)+f(1)+...+f(n-1) &{n>=2} end{cases}
f(n)={1f(0)+f(1)+...+f(n−1)n=0,1n>=2
方法2:既然在
n
>
=
2
n>=2
n>=2时,
(1)
f
(
n
)
=
f
(
0
)
+
f
(
1
)
+
.
.
.
+
f
(
n
−
1
)
f(n)=f(0)+f(1)+...+f(n-1) tag{1}
f(n)=f(0)+f(1)+...+f(n−1)(1)
就是说,
(2)
f
(
n
−
1
)
=
f
(
0
)
+
f
(
1
)
+
.
.
.
+
f
(
n
−
2
)
f(n-1)=f(0)+f(1)+...+f(n-2) tag{2}
f(n−1)=f(0)+f(1)+...+f(n−2)(2)
把
(
2
)
(2)
(2)式代入
(
1
)
(1)
(1)式可得
f
(
n
)
=
2
∗
f
(
n
−
1
)
f(n)=2*f(n-1)
f(n)=2∗f(n−1),所以可以更加简洁一些。时间复杂度一下从
O
(
n
2
)
O(n^2)
O(n2)降到
O
(
n
)
O(n)
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]
最后
以上就是稳重秋天最近收集整理的关于剑指Offer:变态跳台阶Java/Python1.题目描述2.算法描述3.代码描述的全部内容,更多相关剑指Offer:变态跳台阶Java/Python1内容请搜索靠谱客的其他文章。
发表评论 取消回复