Title

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。

每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個(gè)正整數(shù)。

示例 1：

輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。

1 階 + 1 階

2 階

示例 2：

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。

1 階 + 1 階 + 1 階

1 階 + 2 階

2 階 + 1 階

Solve

遞歸

遞歸的思路就比較簡(jiǎn)單了，但是一般第一個(gè)能想到的方法都會(huì)超時(shí)。

def climbStairs_recursion(self, n: int) -> int:def solve(num):if num == 0:return 1if num < 0:return 0return solve(num - 1) + solve(num - 2)return solve(n)

動(dòng)態(tài)規(guī)劃

用f(x)表示爬到第x級(jí)臺(tái)階的方案數(shù)，考慮最后一步可能跨了一級(jí)臺(tái)階，也可能跨了兩級(jí)臺(tái)階，可以列出如下式子：$$f(x)=f(x?1)+f(x?2)$$這就是動(dòng)態(tài)規(guī)劃的轉(zhuǎn)移方程，它意味著爬到第x級(jí)臺(tái)階的方案數(shù)是爬到第x-1級(jí)和爬到第x-2級(jí)臺(tái)階方案數(shù)的總和。

下面我們來討論邊界條件，從第0級(jí)開始：f(0)=1，從第0級(jí)到第1級(jí)只有一種解決方案，即爬1級(jí)，所以f(1)=1，以這兩個(gè)作為邊界條件就可以繼續(xù)往后推導(dǎo)出第n級(jí)的解決方案。

我們不妨寫幾項(xiàng)來驗(yàn)證一下，根據(jù)轉(zhuǎn)移方程得到 f(2) = 2，f(3) = 3，f(4) = 5…我們把這些情況都枚舉出來，發(fā)現(xiàn)計(jì)算的結(jié)果是正確的。

通過轉(zhuǎn)移方程和邊界條件給出一個(gè)時(shí)間復(fù)雜度和空間復(fù)雜度都是 O(n) 的實(shí)現(xiàn)，但是由于這里的 f(x) 只和 f(x - 1) 與 f(x - 2) 有關(guān)，所以我們可以用「滾動(dòng)數(shù)組思想」把空間復(fù)雜度優(yōu)化成 O(1)。

def climbStairs_dynamic_programming(self, n: int) -> int:f0, f1, ans = 0, 0, 1for i in range(1, n + 1):f0 = f1f1 = ansans = f0 + f1return ans

復(fù)雜度分析

時(shí)間復(fù)雜度：循環(huán)執(zhí)行 n 次，每次花費(fèi)常數(shù)的時(shí)間代價(jià)，故漸進(jìn)時(shí)間復(fù)雜度為 O(n)。
空間復(fù)雜度：這里只用了常數(shù)個(gè)變量作為輔助空間，故漸進(jìn)空間復(fù)雜度為 O(1)。

矩陣快速冪

動(dòng)態(tài)規(guī)劃方法的時(shí)間復(fù)雜度為O(n)，只適用于n比較小的情況，在n變大之后，O(n)的時(shí)間復(fù)雜度會(huì)讓這個(gè)算法看起來有些捉襟見肘，我們可以用「矩陣快速冪」的方法來優(yōu)化這個(gè)過程。

首先我們可以構(gòu)建這樣一個(gè)遞推關(guān)系：$$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}f(n)\\ f(n?1)\end{array}\right]=\left[\begin{array}{c}f(n)+f(n?1)\\ f(n)\end{array}\right]=\left[\begin{array}{c}f(n+1)\\ f(n)\end{array}\right]$$

因此：$$\left[\begin{array}{c}f(n+1)\\ f(n)\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}f(n)\\ f(n?1)\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^2\left[\begin{array}{c}f(n?1)\\ f(n?2)\end{array}\right]=...={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n\left[\begin{array}{c}f(1)\\ f(0)\end{array}\right]$$

令：$$M=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$$因此，我們只要快速計(jì)算矩陣M的n次冪，就可以得到f(n)得值。

def climbStairs_matrix_fast_power(self, n: int) -> int:def multiply(matrixA, matrixB):ans = []for i in range(2):ans.append([])for j in range(2):ans[i].append(matrixA[i][0] * matrixB[0][j] + matrixA[i][1] * matrixB[1][j])return ansdef solve(matrix, num):ret = [[1, 0], [0, 1]]while num > 0:if (num & 1) == 1:ret = multiply(ret, matrix)num >>= 1matrix = multiply(matrix, matrix)return retM = [[1, 1], [1, 0]]res = solve(M, n)return res[0][0]

復(fù)雜度分析

時(shí)間復(fù)雜度：同快速冪，O(log n)。
空間復(fù)雜度：O(1)。

總結(jié)

以上是生活随笔為你收集整理的LeetCode Algorithm 70. 爬楼梯的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。