70.爬樓梯 https://leetcode-cn.com/problems/climbing-stairs/

假設你正在爬樓梯。需要 n?階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數。

示例 1：

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

示例 2：

輸入： 3 輸出： 3 解釋： 有三種方法可以爬到樓頂。 1. 1 階 + 1 階 + 1 階 2. 1 階 + 2 階 3. 2 階 + 1 階

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps

Example 2:

Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step

?

Constraints:

• 1 <= n <= 45

題解：

1. 動態規劃法求解：

本問題其實常規解法可以分成多個子問題，爬第n階樓梯的方法數量，等于 2 部分之和：a. 爬上` n-1` 階樓梯的方法數量q。因為再爬1階就能到第n階b. 爬上` n-2` 階樓梯的方法數量p。因為再爬2階就能到第n階 所以我們得到公式 r = p + q 同時需要初始化 r=1 和p=0,q=0。 注意：初始值的設置和循環條件有關系。

時間復雜度：O(n)
C語言解法：

int climbStairs(int n){int p = 0, q = 0, r = 1;for (int i = 1; i <= n; ++i) {p = q; q = r; r = p + q;}return r; }

2. 斐波那契數列
如果觀察數學規律，可知本題是斐波那契數列，那么用斐波那契數列的公式即可解決問題，公式如下：

時間復雜度：O(logn)

Java實現：

class Solution {public int climbStairs(int n) {double sqrt_5 = Math.sqrt(5);double fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);return (int)(fib_n / sqrt_5);} }

聲明：感謝畫手大鵬提供的思路： https://leetcode-cn.com/problems/climbing-stairs/solution/hua-jie-suan-fa-70-pa-lou-ti-by-guanpengchn/

總結

以上是生活随笔為你收集整理的[算法笔记] 爬楼梯的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。