一篇帶你了解DP入門之爬樓梯
爬樓梯
力扣題目鏈接：https://leetcode-cn.com/problems/climbing-stairs
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢?
注意：給定 n 是一個正整數。
示例 1：
- 輸入：2
- 輸出：2
- 解釋：有兩種方法可以爬到樓頂。
- 1 階 + 1 階
- 2 階
示例 2：
- 輸入：3
- 輸出：3
- 解釋：有三種方法可以爬到樓頂。
- 1 階 + 1 階 + 1 階
- 1 階 + 2 階
- 2 階 + 1 階
思路
本題大家如果沒有接觸過的話，會感覺比較難，多舉幾個例子，就可以發現其規律。
爬到第一層樓梯有一種方法，爬到二層樓梯有兩種方法。
那么第一層樓梯再跨兩步就到第三層 ，第二層樓梯再跨一步就到第三層。
所以到第三層樓梯的狀態可以由第二層樓梯 和 到第一層樓梯狀態推導出來，那么就可以想到動態規劃了。
我們來分析一下，動規五部曲：
定義一個一維數組來記錄不同樓層的狀態
確定dp數組以及下標的含義
dp[i]：爬到第i層樓梯，有dp[i]種方法
確定遞推公式
如果可以推出dp[i]呢?
從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 - 1] + dp[i - 2] 。
在推導dp[i]的時候，一定要時刻想著dp[i]的定義，否則容易跑偏。
這體現出確定dp數組以及下標的含義的重要性!
dp數組如何初始化
在回顧一下dp[i]的定義：爬到第i層樓梯，有dp[i]中方法。
那么i為0，dp[i]應該是多少呢，這個可以有很多解釋，但都基本是直接奔著答案去解釋的。
例如強行安慰自己爬到第0層，也有一種方法，什么都不做也就是一種方法即：dp[0] = 1，相當于直接站在樓頂。
但總有點牽強的成分。
那還這么理解呢：我就認為跑到第0層，方法就是0啊，一步只能走一個臺階或者兩個臺階，然而樓層是0，直接站樓頂上了，就是不用方法，dp[0]就應該是0.
其實這么爭論下去沒有意義，大部分解釋說dp[0]應該為1的理由其實是因為dp[0]=1的話在遞推的過程中i從2開始遍歷本題就能過，然后就往結果上靠去解釋dp[0] = 1。
從dp數組定義的角度上來說，dp[0] = 0 也能說得通。
需要注意的是：題目中說了n是一個正整數，題目根本就沒說n有為0的情況。
所以本題其實就不應該討論dp[0]的初始化!
我相信dp[1] = 1，dp[2] = 2，這個初始化大家應該都沒有爭議的。
所以我的原則是：不考慮dp[0]如果初始化，只初始化dp[1] = 1，dp[2] = 2，然后從i = 3開始遞推，這樣才符合dp[i]的定義。
確定遍歷順序
從遞推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍歷順序一定是從前向后遍歷的
舉例推導dp數組
舉例當n為5的時候，dp table(dp數組)應該是這樣的
爬樓梯
如果代碼出問題了，就把dp table 打印出來，看看究竟是不是和自己推導的一樣。
此時大家應該發現了，這不就是斐波那契數列么!
唯一的區別是，沒有討論dp[0]應該是什么，因為dp[0]在本題沒有意義!
以上五部分析完之后，C++代碼如下：
- // 版本一
- class Solution {
- public:
- int climbStairs(int n) {
- if (n <= 1) return n; // 因為下面直接對dp[2]操作了，防止空指針
- vector<int> dp(n + 1);
- dp[1] = 1;
- dp[2] = 2;
- for (int i = 3; i <= n; i++) { // 注意i是從3開始的
- dp[i] = dp[i - 1] + dp[i - 2];
- }
- return dp[n];
- }
- };
- 時間復雜度：
- 空間復雜度：
當然依然也可以，優化一下空間復雜度，代碼如下：
- // 版本二
- class Solution {
- public:
- int climbStairs(int n) {
- if (n <= 1) return n;
- int dp[3];
- dp[1] = 1;
- dp[2] = 2;
- for (int i = 3; i <= n; i++) {
- int sum = dp[1] + dp[2];
- dp[1] = dp[2];
- dp[2] = sum;
- }
- return dp[2];
- }
- };
- 時間復雜度：
- 空間復雜度：
后面將講解的很多動規的題目其實都是當前狀態依賴前兩個，或者前三個狀態，都可以做空間上的優化，但我個人認為面試中能寫出版本一就夠了哈，清晰明了，如果面試官要求進一步優化空間的話，我們再去優化。
因為版本一才能體現出動規的思想精髓，遞推的狀態變化。
拓展
這道題目還可以繼續深化，就是一步一個臺階，兩個臺階，三個臺階，直到 m個臺階，有多少種方法爬到n階樓頂。
這又有難度了，這其實是一個完全背包問題，但力扣上沒有這種題目，所以后續我在講解背包問題的時候，今天這道題還會拿從背包問題的角度上來再講一遍。
這里我先給出我的實現代碼：
- class Solution {
- public:
- int climbStairs(int n) {
- vector<int> dp(n + 1, 0);
- dp[0] = 1;
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= m; j++) { // 把m換成2，就可以AC爬樓梯這道題
- if (i - j >= 0) dp[i] += dp[i - j];
- }
- }
- return dp[n];
- }
- };
代碼中m表示最多可以爬m個臺階。
以上代碼不能運行哈，我主要是為了體現只要把m換成2，粘過去，就可以AC爬樓梯這道題，不信你就粘一下試試，哈哈。
此時我就發現一個絕佳的大廠面試題，第一道題就是單純的爬樓梯，然后看候選人的代碼實現，如果把dp[0]的定義成1了，就可以發難了，為什么dp[0]一定要初始化為1，此時可能候選人就要強行給dp[0]應該是1找各種理由。那這就是一個考察點了，對dp[i]的定義理解的不深入。
然后可以繼續發難，如果一步一個臺階，兩個臺階，三個臺階，直到 m個臺階，有多少種方法爬到n階樓頂。這道題目leetcode上并沒有原題，絕對是考察候選人算法能力的絕佳好題。
這一連套問下來，候選人算法能力如何，面試官心里就有數了。
其實大廠面試最喜歡問題的就是這種簡單題，然后慢慢變化，在小細節上考察候選人。
總結
這道題目和動態規劃：斐波那契數題目基本是一樣的，但是會發現本題相比動態規劃：斐波那契數難多了，為什么呢?
關鍵是 動態規劃：斐波那契數 題目描述就已經把動規五部曲里的遞歸公式和如何初始化都給出來了，剩下幾部曲也自然而然的推出來了。
而本題，就需要逐個分析了，大家現在應該初步感受出關于動態規劃，你該了解這些!里給出的動規五部曲了。
簡單題是用來掌握方法論的，例如昨天斐波那契的題目夠簡單了吧，但昨天和今天可以使用一套方法分析出來的，這就是方法論!
所以不要輕視簡單題，那種憑感覺就刷過去了，其實和沒掌握區別不大，只有掌握方法論并說清一二三，才能觸類旁通，舉一反三哈!
就醬，循序漸進學算法，認準「代碼隨想錄」!
其他語言版本
Java
- class Solution {
- public int climbStairs(int n) {
- // 跟斐波那契數列一樣
- if(n <= 2) return n;
- int a = 1, b = 2, sum = 0;
- for(int i = 3; i <= n; i++){
- sum = a + b;
- a = b;
- b = sum;
- }
- return b;
- }
- }
- // 常規方式
- 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];
- }
- // 用變量記錄代替數組
- public int climbStairs(int n) {
- int a = 0, b = 1, c = 0; // 默認需要1次
- for (int i = 1; i <= n; i++) {
- c = a + b; // f(i - 1) + f(n - 2)
- a = b; // 記錄上一輪的值
- b = c; // 向后步進1個數
- }
- return c;
- }
Python
- class Solution:
- def climbStairs(self, n: int) -> int:
- # dp[i]表示爬到第i級樓梯的種數， (1, 2) (2, 1)是兩種不同的類型
- dp = [0] * (n + 1)
- dp[0] = 1
- for i in range(n+1):
- for j in range(1, 3):
- if i>=j:
- dp[i] += dp[i-j]
- return dp[-1]
Go
- func climbStairs(n int) int {
- if n==1{
- return 1
- }
- dp:=make([]int,n+1)
- dp[1]=1
- dp[2]=2
- for i:=3;i<=n;i++{
- dp[i]=dp[i-1]+dp[i-2]
- }
- return dp[n]
- }
Javascript
- var climbStairs = function(n) {
- // dp[i] 為第 i 階樓梯有多少種方法爬到樓頂
- // dp[i] = dp[i - 1] + dp[i - 2]
- let dp = [1 , 2]
- for(let i = 2; i < n; i++) {
- dp[i] = dp[i - 1] + dp[i - 2]
- }
- return dp[n - 1]
- };
