思路

多舉幾個例子，就可以發現其規律。

爬到第一層樓梯有一種方法，爬到二層樓梯有兩種方法。

那么第一層樓梯再跨兩步就到第三層 ，第二層樓梯再跨一步就到第三層。

所以到第三層樓梯的狀態可以由第二層樓梯 和 到第一層樓梯狀態推導出來，那么就可以想到動態規劃了。

我們來分析一下，動規五部曲：

定義一個一維數組來記錄不同樓層的狀態

1、確定dp數組以及下標的含義

dp[i]： 爬到第i層樓梯，有dp[i]種方法

2、確定遞推公式

從dp[i]的定義可以看出，dp[i] 可以有兩個方向推出來。

首先是dp[i - 1]，上i-1層樓梯，有dp[i - 1]種方法，那么再一步跳一個臺階不就是dp[i]了么。

還有就是dp[i - 2]，上i-2層樓梯，有dp[i - 2]種方法，那么再一步跳兩個臺階不就是dp[i]了么。

所以dp[i] = dp[i - 1] + dp[i - 2] 。

在推導dp[i]的時候，一定要時刻想著dp[i]的定義，否則容易跑偏。

這體現出確定dp數組以及下標的含義的重要性！

3、dp數組如何初始化

在回顧一下dp[i]的定義：爬到第i層樓梯，有dp[i]中方法。

不考慮dp[0]初始化，只初始化dp[1] = 1，dp[2] = 2，然后從i = 3開始遞推

4、確定遍歷順序

從遞推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍歷順序一定是從前向后遍歷的

5、舉例推導dp數組

舉例當n為5的時候，dp table（dp數組）應該是這樣的

版本一

時間復雜度：O(n) 空間復雜度：O(n) class Solution { public:int climbStairs(int n) {if(n<=2) return n;vector<int> dp(n+1);dp[1]=1;dp[2]=2;for(int ii=3;ii<=n;ii++){dp[ii]=dp[ii-1]+dp[ii-2];}return dp[n];} };

優化

時間復雜度：O(n) 空間復雜度：O(1) class Solution { public:int climbStairs(int n) {if(n<=2) return n;int dp[3];dp[1]=1;dp[2]=2;for(int ii=3;ii<=n;ii++){int sum=dp[1]+dp[2];dp[1]=dp[2];dp[2]=sum;}return dp[2];} };

總結

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

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