經(jīng)典企業(yè)面試題——爬樓梯

　　有n層的臺階，一開始你站在第0層，每次可以爬兩層或者一層。請問爬到第n層有多少種不同的方法?

　　Follow Up Question: 如果每次可以爬兩層，和倒退一層，同一個位置不能重復(fù)走，請問爬到第n層有多少種不同的方法?

　　答：這道題屬于簡單的數(shù)組一維動態(tài)規(guī)劃

　　1. State:f[i] 表示爬到第i層的方法數(shù)目。

　　2. Function: f[i] = f[i-1] + f[i-2] 第i層的方法數(shù)目等于第i-1層數(shù)目加上第i-2層數(shù)目

　　3. Intialize: f[0] = 1, f[1] =1 初始化 最開始沒有爬和第一層的方法數(shù)目為1.

　　4. Answer: f[n] 爬到第n層有多少種不同的方法

　　Follow Up Question:

　　這道題與原來的題相比提升了一個難度，主要是倒退一層，這個地方可能會違背動態(tài)規(guī)劃無后效性的原則。 那么我們要怎么轉(zhuǎn)化呢?

　　由條件：同一個位置不能重復(fù)走。我們可以知道如果要退步的話，不能退兩層以上，因?yàn)橛脙刹酵藘蓪釉僖徊角斑M(jìn)兩層，那就會走相同的位置。所以我們最多只能退后一步。

　　那么題目的條件就可以轉(zhuǎn)換兩種情況，

　　a.跳兩層(前進(jìn)兩層)。

　　b.退一層跳兩層 (前進(jìn)一層)。

　　1. State:f[i][0] 表示最后一步是跳兩層情況下爬到第i層的方法數(shù)目。f[i][1] 表示最后是一步是退一層跳兩層的情況下爬到第i層的方法數(shù)目。

　　2. Function: f[i+1][1] = f[i][0] 最后一步是退一層跳兩層的情況下爬到第i+1層的方法數(shù)目等于從第i層情況a的數(shù)目跳兩層退一層。這里不能考慮第i層的情況b的方法數(shù)，因?yàn)榈趇層情況b的數(shù)目是從第i+1層退一步得到的。

　　f[i+2][0] = f[i][0]+f[i][1] 最后一步是退一層跳兩層的情況下爬到第i+2層的方法數(shù)目等于第i層所有情況跳兩層。

　　3. Intialize: f[0][0]=1初始化最開始沒有爬的方法數(shù)目為1.

　　4. Answer: f[n][0]+f[n][1] 爬到第n層a、b兩種不同的方法的總和

【經(jīng)典企業(yè)面試題——爬樓梯】相關(guān)文章：

爬樓梯膝蓋疼怎么辦07-04

Microsoft面試題09-04

iOS面試題07-10

公司面試題09-12

hibernate面試題10-18

英語面試題精選06-13

小升初面試題06-10

PHP面試題10-14

500強(qiáng)企業(yè)面試題，如何賣掉情人節(jié)后的玫瑰花？08-30

小升初面試題型08-24