題目鏈接

https://leetcode-cn.com/problems/climbing-stairs/

題目描述

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

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

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

示例 1：

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

示例 2：

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

解題方案

第一種思路

• 標(biāo)簽：數(shù)學(xué)

• 如果觀察數(shù)學(xué)規(guī)律，可知本題是斐波那契數(shù)列，那么用斐波那契數(shù)列的公式即可解決問題，公式如下：

• 時間復(fù)雜度：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);
   }
}

• JavaScript版本

/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
   const sqrt_5 = Math.sqrt(5);
   const fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
   return Math.round(fib_n / sqrt_5);
};

第二種思路

• 標(biāo)簽：動態(tài)規(guī)劃

• 本問題其實常規(guī)解法可以分成多個子問題，爬第n階樓梯的方法數(shù)量，等于2部分之和

1. 爬上n-1階樓梯的方法數(shù)量。因為再爬1階就能到第n階

2. 爬上n-2階樓梯的方法數(shù)量，因為再爬2階就能到第n階

• 所以我們得到公式dp[n] = dp[n-1] + dp[n-2]

• 同時需要初始化dp[0]=1和dp[1]=1

• 時間復(fù)雜度：O(n)

第二種思路代碼

• Java版本

class Solution {
   public int climbStairs(int n) {
       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];
   }
}

• JavaScript版本

/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
   const dp = [];
   dp[0] = 1;
   dp[1] = 1;
   for(let i = 2; i <= n; i++) {
       dp[i] = dp[i - 1] + dp[i - 2];
   }
   return dp[n];
};

畫解