通知：我將公眾號文章和學習相關的資料整理到了Github ：https://github.com/youngyangyang04/leetcode-master，方便大家在電腦上學習，可以fork到自己倉庫，順便也給個star支持一波吧！

之前講這道題目的時候，因為還沒有講背包問題，所以就只是講了一下爬樓梯最直接的動規(guī)方法（斐波那契）。

這次終于講到了背包問題，我選擇帶錄友們再爬一次樓梯！

此情此景，借用一下《無間道》的臺詞 哈哈哈。

70. 爬樓梯

鏈接：https://leetcode-cn.com/problems/climbing-stairs/

假設你正在爬樓梯。需要 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 階

思路

這道題目 我們在動態(tài)規(guī)劃：爬樓梯 中已經(jīng)講過一次了，原題其實是一道簡單動規(guī)的題目。

既然這么簡單為什么還要講呢，其實本題稍加改動就是一道面試好題。

改為：每次可以爬 1 、 2或者m 個臺階。問有多少種不同的方法可以爬到樓頂呢？

1階，2階，m階就是物品，樓頂就是背包。

每一階可以重復使用，例如跳了1階，還可以繼續(xù)跳1階。

問跳到樓頂有幾種方法其實就是問裝滿背包有幾種方法。

此時大家應該發(fā)現(xiàn)這就是一個完全背包問題了！

和昨天的題目動態(tài)規(guī)劃：377. 組合總和 Ⅳ基本就是一道題了。

動規(guī)五部曲分析如下：

1. 確定dp數(shù)組以及下標的含義

dp[i]：爬到有i個臺階的樓頂，有dp[i]種方法。

1. 確定遞推公式

在動態(tài)規(guī)劃：494.目標和 、 動態(tài)規(guī)劃：518.零錢兌換II、動態(tài)規(guī)劃：377. 組合總和 Ⅳ中我們都講過了，求裝滿背包有幾種方法，遞推公式一般都是dp[i] = dp[i - nums[j]];

本題呢，dp[i]有幾種來源，dp[i - 1]，dp[i - 2]，dp[i - 3] 等等，即：dp[i - j]

那么遞推公式為：dp[i] = dp[i - j]

1. dp數(shù)組如何初始化

既然遞歸公式是 dp[i] = dp[i - j]，那么dp[0] 一定為1，dp[0]是遞歸中一切數(shù)值的基礎所在，如果dp[0]是0的話，其他數(shù)值都是0了。

下標非0的dp[i]初始化為0，因為dp[i]是靠dp[i-j]累計上來的，dp[i]本身為0這樣才不會影響結(jié)果

1. 確定遍歷順序

這是背包里求排列問題，即：1、2 步 和 2、1 步都是上三個臺階，但是這兩種方法不！

所以需將target放在外循環(huán)，將nums放在內(nèi)循環(huán)。

每一步可以走多次，這是完全背包，內(nèi)循環(huán)需要從前向后遍歷。

1. 舉例來推導dp數(shù)組

介于本題和動態(tài)規(guī)劃：377. 組合總和 Ⅳ幾乎是一樣的，這里我就不再重復舉例了。

以上分析完畢，C 代碼如下：

代碼中m表示最多可以爬m(xù)個臺階，代碼中把m改成2就是本題70.爬樓梯可以AC的代碼了。

總結(jié)

本題看起來是一道簡單題目，稍稍進階一下其實就是一個完全背包！

如果我來面試的話，我就會先給候選人出一個 本題原題，看其表現(xiàn)，如果順利寫出來，進而在要求每次可以爬[1 - m]個臺階應該怎么寫。

順便再考察一下兩個for循環(huán)的嵌套順序，為什么target放外面，nums放里面。

這就能考察對背包問題本質(zhì)的掌握程度，候選人是不是刷題背公式，一眼就看出來了。

這么一連套下來，如果候選人都能答出來，相信任何一位面試官都是非常滿意的。

本題代碼不長，題目也很普通，但稍稍一進階就可以考察完全背包，而且題目進階的內(nèi)容在leetcode上并沒有原題，一定程度上就可以排除掉刷題黨了，簡直是面試題目的絕佳選擇！

力扣刷題指南：https://github.com/youngyangyang04/leetcode-master