第 10-1 題：跳臺(tái)階（斐波拉契數(shù)列辆亏、滾動(dòng)變量）
傳送門：AcWing：跳臺(tái)階，湃廴危客網(wǎng) online judge 地址褒链，牛客網(wǎng) online judge 地址疑苔。
輸入一個(gè)整數(shù)
甫匹，求斐波那契數(shù)列的第
假定從
開始惦费，第
)
樣例：
輸入整數(shù)
返回
。
一只青蛙一次可以跳上 1 級(jí)臺(tái)階薪贫，也可以跳上 2 級(jí)恍箭。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。
思路：這題的數(shù)據(jù)范圍很小瞧省，我們直接模擬即可扯夭。當(dāng)數(shù)據(jù)范圍很大時(shí)，就需要采用其他方式了鞍匾，可以參考求解斐波那契數(shù)列的若干方法交洗。寫成動(dòng)態(tài)規(guī)劃，如果使用遞歸橡淑，一定要加上緩存构拳，否則會(huì)重復(fù)求解子問題，導(dǎo)致效率低下梁棠。
- 題目背景是斐波拉契數(shù)列置森。
- 在實(shí)現(xiàn)的時(shí)候思考如何節(jié)約空間，其實(shí)使用常數(shù)級(jí)別的輔助空間就可以了符糊。
時(shí)間復(fù)雜度：總共需要計(jì)算 次凫海，所以時(shí)間復(fù)雜度是
。
Python 代碼1：用兩個(gè)變量滾動(dòng)式往后計(jì)算男娄， 表示第
項(xiàng)盐碱，
表示第
項(xiàng)。則令
表示第
項(xiàng)沪伙，然后讓
、
順次往后移一位县好。
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
# “滾動(dòng)變量”：接下來重新定義 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
參考資料：面試官問你斐波那契數(shù)列的時(shí)候不要高興得太早。書上斐波拉契數(shù)列數(shù)列空間更省的寫法缕贡，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);
}
}
}
