經(jīng)典企業(yè)面試題——爬樓梯
有n層的臺(tái)階，一開始你站在第0層，每次可以爬兩層或者一層。請(qǐng)問爬到第n層有多少種不同的方法?
Follow Up Question: 如果每次可以爬兩層，和倒退一層，同一個(gè)位置不能重復(fù)走，請(qǐng)問爬到第n層有多少種不同的方法?
答：這道題屬于簡(jiǎn)單的數(shù)組一維動(dòng)態(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:
這道題與原來的題相比提升了一個(gè)難度，主要是倒退一層，這個(gè)地方可能會(huì)違背動(dòng)態(tài)規(guī)劃無后效性的原則。 那么我們要怎么轉(zhuǎn)化呢?
由條件：同一個(gè)位置不能重復(fù)走。我們可以知道如果要退步的話，不能退兩層以上，因?yàn)橛脙刹酵藘蓪釉僖徊角斑M(jìn)兩層，那就會(huì)走相同的位置。所以我們最多只能退后一步。
那么題目的條件就可以轉(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兩種不同的方法的總和
http://m.sctltx.cn/【經(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