[剑指 Offer 第 2 版第 10 题] “跳台阶”做题记录
[剑指 Offer 第 2 版第 10 题] “跳台阶”做题记录
第 10-1 题:跳台阶(斐波拉契数列、滚动变量)
传送门:AcWing:跳台阶,牛客网 online judge 地址,牛客网 online judge 地址。
输入一个整数 n ,求斐波那契数列的第 n 项。
假定从 0 开始,第 0 项为 0 。(n \\le 39)
样例:
输入整数 n=5
返回 5。
一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
思路:这题的数据范围很小,我们直接模拟即可。当数据范围很大时,就需要采用其他方式了,可以参考求解斐波那契数列的若干方法。写成动态规划,如果使用递归,一定要加上缓存,否则会重复求解子问题,导致效率低下。
- 题目背景是斐波拉契数列。
- 在实现的时候思考如何节约空间,其实使用常数级别的辅助空间就可以了。
时间复杂度:总共需要计算 n 次,所以时间复杂度是 O(n) 。
Python 代码1:用两个变量滚动式往后计算,a 表示第 n−1 项,b 表示第 n 项。则令 c=a+b 表示第 n+1 项,然后让 a、b 顺次往后移一位。
class Solution(object):
def Fibonacci(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 0
if n == 1:
return 1
a = 0
b = 1
while n:
c = a + b
# “滚动变量”:接下来重新定义 a 和 b
a = b
b = c
n -= 1
return a
Python 代码2:Python 语法糖,了解即可
class Solution(object):
def Fibonacci(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 0
if n == 1:
return 1
a = 0
b = 1
while n:
a , b = a + b , a
n -= 1
return a
Python 代码3:
class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
a = 0
b = 1
while n:
a , b = b , a + b
n -= 1
return b
参考资料:面试官问你斐波那契数列的时候不要高兴得太早。书上斐波拉契数列数列空间更省的写法,P76。
Java 代码:
public class Solution {
// 1 1 2 3 5 8
// 0 1 2 3 4 5
public int Fibonacci(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
public static void main(String[] args) {
Solution solution = new Solution();
int fibonacci = solution.Fibonacci(5);
System.out.println(fibonacci);
}
}
Java 代码:
public class Solution {
// 1 2 3 5 8
// 1 2 3 4 5
public int JumpFloor(int target) {
int n = target;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// i j (i+j)
// 1 2 3 5
// 1 2 3 4
public int JumpFloor1(int target) {
if (target == 1) {
return 1;
}
int n = target;
int i = 1;
int j = 2;
int temp;
for (int k = 3; k <= n; k++) {
temp = j;
j = i + j;
i = temp;
}
return j;
}
public static void main(String[] args) {
Solution solution = new Solution();
for (int i = 1; i < 5; i++) {
int jumpFloor = solution.JumpFloor1(i);
System.out.println(jumpFloor);
}
}
}
作者:liweiwei1419
来源:https://liweiwei1419.github.io/sword-for-offer/
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「方志朋」,公众号后台回复「666」 免费领取我精心整理的进阶资源教程

本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com