- 相關推薦
經典企業面試題——爬樓梯
有n層的臺階，一開始你站在第0層，每次可以爬兩層或者一層。請問爬到第n層有多少種不同的方法?
Follow Up Question: 如果每次可以爬兩層，和倒退一層，同一個位置不能重復走，請問爬到第n層有多少種不同的方法?
答：這道題屬于簡單的數組一維動態規劃
1. State:f[i] 表示爬到第i層的方法數目。
2. Function: f[i] = f[i-1] + f[i-2] 第i層的方法數目等于第i-1層數目加上第i-2層數目
3. Intialize: f[0] = 1, f[1] =1 初始化 最開始沒有爬和第一層的方法數目為1.
4. Answer: f[n] 爬到第n層有多少種不同的方法
Follow Up Question:
這道題與原來的題相比提升了一個難度，主要是倒退一層，這個地方可能會違背動態規劃無后效性的原則。 那么我們要怎么轉化呢?
由條件：同一個位置不能重復走。我們可以知道如果要退步的話，不能退兩層以上，因為用兩步退兩層再一步前進兩層，那就會走相同的位置。所以我們最多只能退后一步。
那么題目的條件就可以轉換兩種情況，
a.跳兩層(前進兩層)。
b.退一層跳兩層 (前進一層)。
1. State:f[i][0] 表示最后一步是跳兩層情況下爬到第i層的方法數目。f[i][1] 表示最后是一步是退一層跳兩層的情況下爬到第i層的方法數目。
2. Function: f[i+1][1] = f[i][0] 最后一步是退一層跳兩層的情況下爬到第i+1層的方法數目等于從第i層情況a的數目跳兩層退一層。這里不能考慮第i層的情況b的方法數，因為第i層情況b的數目是從第i+1層退一步得到的。
f[i+2][0] = f[i][0]+f[i][1] 最后一步是退一層跳兩層的情況下爬到第i+2層的方法數目等于第i層所有情況跳兩層。
3. Intialize: f[0][0]=1初始化最開始沒有爬的方法數目為1.
4. Answer: f[n][0]+f[n][1] 爬到第n層a、b兩種不同的方法的總和
http://www.ipr-jzsc.com/【經典企業面試題——爬樓梯】相關文章：
爬樓梯膝蓋疼怎么辦07-04
Microsoft面試題09-04
iOS面試題07-10
公司面試題09-12
hibernate面試題10-18
英語面試題精選06-13
小升初面試題06-10
PHP面試題10-14
小升初面試題型08-24