假設(shè)你正在爬樓梯馋吗。需要 n 階你才能到達(dá)樓頂缺猛。
每次你可以爬 1 或 2 個(gè)臺(tái)階拷沸。你有多少種不同的方法可以爬到樓頂呢中姜？
注：n 是一個(gè)正整數(shù)消玄。
示例 1：
輸入： 2
輸出： 2
解釋?zhuān)?有兩種方法可以爬到樓頂。
- 1 階 + 1 階
- 2 階
示例 2：
輸入： 3
輸出： 3
解釋?zhuān)?有三種方法可以爬到樓頂丢胚。
- 1 階 + 1 階 + 1 階
- 1 階 + 2 階
- 2 階 + 1 階
方法一：暴力法
在暴力法中翩瓜，我們將會(huì)把所有可能爬的階數(shù)進(jìn)行組合，也就是 1 和 2 携龟。而在每一步中我們都會(huì)繼續(xù)調(diào)用 climbStairs兔跌，climbStairs 這個(gè)函數(shù)模擬爬 1 階和 2 階的情形，并返回兩個(gè)函數(shù)的返回值之和峡蟋。
climbStairs(i,n) = climbStairs(i + 1, n) + climbStairs(i + 2, n)
其中 i 定義了當(dāng)前階數(shù)坟桅，而 n 定義了目標(biāo)階數(shù)。
class Solution {
public int climbStairs(int n) {
return climbWays(0, n);
}
public int climbWays(int curStair, int totalStair){
if(curStair > totalStair){
return 0;
}
if(curStair == totalStair){
return 1;
}
return climbWays(curStair +1, totalStair) + climbWays(curStair +2, totalStair);
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(2n)蕊蝗。樹(shù)形遞歸的大小為 2n仅乓。
在 n=5 時(shí)的遞歸樹(shù)將是這樣的：
- 空間復(fù)雜度：O(n)。遞歸樹(shù)的深度可以達(dá)到 n 蓬戚。
方法 2：記憶化遞歸
在上一種方法中夸楣，我們計(jì)算每一步的結(jié)果時(shí)出現(xiàn)了冗余。另一種思路是子漩，我們可以把每一步的結(jié)果存儲(chǔ)在 memory 數(shù)組之中豫喧，每當(dāng)函數(shù)再次被調(diào)用，我們就直接從 memory 數(shù)組返回結(jié)果幢泼。
在 memory 數(shù)組的幫助下嘿棘，我們得到了一個(gè)修復(fù)的遞歸樹(shù)，其大小減少到 n 旭绒。
public class Solution {
public int climbStairs(int n) {
int memo[] = new int[n + 1];
return climb_Stairs(0, n, memo);
}
public int climb_Stairs(int i, int n, int memo[]) {
if (i > n) {
return 0;
}
if (i == n) {
return 1;
}
if (memo[i] > 0) {
return memo[i];
}
memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
return memo[i];
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n) 鸟妙。樹(shù)形遞歸的大小可以達(dá)到 n。
- 空間復(fù)雜度：O(n) 挥吵。遞歸樹(shù)的深度可以達(dá)到 n重父。
方法 3：動(dòng)態(tài)規(guī)劃
不難發(fā)現(xiàn)，這個(gè)問(wèn)題可以被分解為一些包含最優(yōu)子結(jié)構(gòu)的子問(wèn)題忽匈，即它的最優(yōu)解可以從其子問(wèn)題的最優(yōu)解來(lái)有效地構(gòu)建房午，我們可以使用動(dòng)態(tài)規(guī)劃來(lái)解決這一問(wèn)題。
第 ii 階可以由以下兩種方法得到：
在第 (i-1) 階后向上爬 1 階丹允。
在第 (i-2) 階后向上爬 2 階郭厌。
所以到達(dá)第 i 階的方法總數(shù)就是到第 (i?1) 階和第 (i?2) 階的方法數(shù)之和袋倔。
令 dp[i] 表示能到達(dá)第 i 階的方法總數(shù)：
dp[i]=dp[i-1]+dp[i-2]
public class Solution {
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n)，單循環(huán)到 n 折柠。
- 空間復(fù)雜度：O(n)宾娜，dp 數(shù)組用了 n 的空間。
方法 4: 斐波那契數(shù)
在上述方法中扇售，我們使用 dp 數(shù)組前塔，其中 dp[i]=dp[i-1]+dp[i-2]〕斜可以很容易通過(guò)分析得出 dp[i] 其實(shí)就是第 i 個(gè)斐波那契數(shù)华弓。
Fib(n)=Fib(n-1)+Fib(n-2)
現(xiàn)在我們必須找出以 1 和 2 作為第一項(xiàng)和第二項(xiàng)的斐波那契數(shù)列中的第 n 個(gè)數(shù)，也就是說(shuō) Fib(1)=1 且 Fib(2)=2困乒。
public class Solution {
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
int first = 1;
int second = 2;
for (int i = 3; i <= n; i++) {
int third = first + second;
first = second;
second = third;
}
return second;
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n)寂屏。單循環(huán)到 n，需要計(jì)算第 n 個(gè)斐波那契數(shù)娜搂。
- 空間復(fù)雜度：O(1)凑保。使用常量級(jí)空間。
方法 5: Binets 方法
算法
這里有一種有趣的解法涌攻，它使用矩陣乘法來(lái)得到第 nn 個(gè)斐波那契數(shù)。矩陣形式如下：
令
按照此方法频伤，第 nn 個(gè)斐波那契數(shù)可以由 Qn-1[0,0] 給出恳谎。
讓我們?cè)囍C明一下。
我們可以使用數(shù)學(xué)歸納法來(lái)證明這一方法憋肖。易知因痛，該矩陣給出了第 3 項(xiàng)（基本情況）的正確結(jié)果。由于
這證明基本情況是成立的岸更。
假設(shè)此方法適用于查找第 nn 個(gè)斐波那契數(shù)鸵膏，即 Fn=Qn-1[0,0]，那么：
現(xiàn)在怎炊，我們需要證明在上述兩個(gè)條件為真的情況下谭企，該方法可以有效找出第 (n+1) 個(gè)斐波那契數(shù)，即评肆，F(xiàn)n+1=Qn[0,0]债查。
證明：
從而， Fn+1=Qn[0,0]瓜挽。得證盹廷。
我們需要為我們的問(wèn)題做的唯一改動(dòng)就是將斐波那契數(shù)列的初始項(xiàng)修改為 2 和 1 來(lái)代替原來(lái)的 1 和 0 【贸龋或者俄占，另一種方法是使用相同的初始矩陣 Q 并使用 result = Qn[0,0] 得出最后結(jié)果管怠。發(fā)生這種情況的原因是我們必須使用原斐波那契數(shù)列的第 2 項(xiàng)和第 3 項(xiàng)作為初始項(xiàng)。
public class Solution {
public int climbStairs(int n) {
int[][] q = {{1, 1}, {1, 0}};
int[][] res = pow(q, n);
return res[0][0];
}
public int[][] pow(int[][] a, int n) {
int[][] ret = {{1, 0}, {0, 1}};
while (n > 0) {
if ((n & 1) == 1) {
ret = multiply(ret, a);
}
n >>= 1;
a = multiply(a, a);
}
return ret;
}
public int[][] multiply(int[][] a, int[][] b) {
int[][] c = new int[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
}
}
return c;
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(log(n))缸榄。遍歷 log(n) 位渤弛。
- 空間復(fù)雜度：O(1)。使用常量級(jí)空間碰凶。
方法 6: 斐波那契公式
我們可以使用這一公式來(lái)找出第 n 個(gè)斐波那契數(shù)：
對(duì)于給定的問(wèn)題暮芭，斐波那契序列將會(huì)被定義為 F0 = 1，F(xiàn)1 = 1欲低，F(xiàn)2= 2辕宏，F(xiàn)n+2= Fn+1 + Fn。嘗試解決這一遞歸公式的標(biāo)準(zhǔn)方法是設(shè)出 Fn 砾莱，其形式為 Fn= an瑞筐。然后，自然有 Fn+1 = an+1和 Fn+2= an+2腊瑟，所以方程可以寫(xiě)作 an+2= an+1+ an聚假。如果我們對(duì)整個(gè)方程進(jìn)行約分，可以得到 a2 = a + 1 或者寫(xiě)成二次方程形式 a2 - a- 1= 0闰非。
對(duì)二次公式求解膘格，我們得到:
一般解采用以下形式：
n = 0時(shí)，有A + B = 1
n = 1時(shí)财松，有
解上述等式瘪贱，我們得到：
將 AA 和 BB 的這些值帶入上述的一般解方程中，可以得到：
public class Solution {
public int climbStairs(int n) {
double sqrt5=Math.sqrt(5);
double fibn=Math.pow((1+sqrt5)/2,n+1)-Math.pow((1-sqrt5)/2,n+1);
return (int)(fibn/sqrt5);
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(log(n))辆毡。pow方法將會(huì)用去 log(n) 的時(shí)間菜秦。
- 空間復(fù)雜度：O(1)。使用常量級(jí)空間舶掖。
