最近在刷題，碰到了上臺(tái)階問(wèn)題菌仁，據(jù)說(shuō)這也是Google的面試題浩习，今天來(lái)整理一下。
問(wèn)題描述
有一樓梯共m級(jí)济丘，若每次只能跨上一級(jí)或二級(jí)谱秽，要走上第m級(jí)，共有多少走法摹迷？
這種問(wèn)題老司機(jī)一看就知道用動(dòng)態(tài)規(guī)劃的思想去求解疟赊，但是小白如我們可怎么辦呢？
不懂動(dòng)態(tài)規(guī)劃峡碉？沒(méi)事近哟，不懂也可以解出來(lái)這個(gè)題目的。不要著急鲫寄，且聽(tīng)我娓娓道來(lái)吉执。
現(xiàn)在不是讓我們求上到m層有多少種走法嗎？好啊塔拳，設(shè)走到m層需要x種走法鼠证，這個(gè)套路大家肯定非常熟悉，中學(xué)數(shù)學(xué)最喜歡設(shè)各種東西靠抑。好量九，現(xiàn)在要開(kāi)始求解x了，首先我們自然會(huì)想到先找找看這個(gè)x跟什么有關(guān)系颂碧，看能不能跟誰(shuí)聯(lián)立一個(gè)方程啥的不就好整了么荠列？
思路是對(duì)的，那x跟誰(shuí)有關(guān)系呢载城？把目光轉(zhuǎn)向題目要求（問(wèn)題本身會(huì)提供有用信息肌似，這是中學(xué)數(shù)學(xué)的套路），我們看到題目說(shuō)每一次只能跨一步或兩步诉瓦，也就是說(shuō)要想到達(dá)m層川队，我們只能從m-1層跨一步上去或者從m-2層跨兩步上去。假設(shè)到達(dá)m-1層有x1種走法睬澡，到達(dá)m-2層有x2種走法固额，那么：
x = x1 + x2
從上式中可以看出所求到達(dá)m層的走法x是依附于到達(dá)m-1層的走法x1和到達(dá)m-2層的走法x2∩反希看到?jīng)]有斗躏，一個(gè)問(wèn)題的解依附于其子問(wèn)題的解（動(dòng)態(tài)規(guī)劃的精髓所在）。也就是說(shuō)只要我們知道了m-1層的走法x1和m-2層的走法x2就能知道到達(dá)m層的走法x了昔脯。
到這里啄糙，大家可能會(huì)問(wèn)了笛臣，那x1 和 x2不也不知道嗎？ x不還是求不出來(lái)么隧饼？恩沈堡，是的，但是既然我們知道m(xù)層的走法能從m - 1層和m-2層的走法求得桑李，那同樣的道理踱蛀，m-1層的走法不也可以從(m-1) - 1和(m-1)-2層的走法求得嗎？m-2層的走法不也可以從(m-2)-1和(m-2)-2層的走法求得嗎贵白？
似不似頭暈乎乎的率拒？來(lái)整個(gè)小栗子看看：
這里我們用一個(gè)數(shù)組Box來(lái)存儲(chǔ)各個(gè)層的走法，Box[i]表示走到第i層有多少種走法禁荒。也即是說(shuō)我們上邊的x猬膨，x1，x2可以用Box[m], Box[m-1], Box[m-2]來(lái)表示呛伴，這樣看起來(lái)是不是更清晰了勃痴。
好了，小栗子來(lái)了热康，現(xiàn)在我給你6個(gè)臺(tái)階沛申，每次只能跨一步或者兩步，問(wèn)有多少種走法到達(dá)第6層姐军？
請(qǐng)看圖：
要到達(dá)第六層铁材，只有兩種可能：
- 跨一個(gè)臺(tái)階從第5層上去
- 跨兩個(gè)臺(tái)階從第4層上去
也就是說(shuō)，要么從第5層上去奕锌；要么從第4層上去著觉。又已知到達(dá)第5層有Box[5]種上法；到達(dá)第4層有Box[4]種上法惊暴。
因此饼丘，上到第6層有 Box[5] + Box[4] 種上法，即
Box[6] = Box[5] + Box[4]
推廣開(kāi)來(lái)辽话，即有：
Box[i] = Box[i - 1] + Box[i - 2], (i > 2)
當(dāng) i = 1時(shí)肄鸽，Box[1] = 1;
當(dāng) i = 2時(shí)，Box[2] = 2;
為啥要加個(gè)條件 i > 2 呢油啤？因?yàn)槟阆氚√瘢绻鹖 = 2，那就有Box[2] = Box[1] + Box[0]村砂；i = 1，即有Box[1] = Box[0] + Box[-1]屹逛。而我們存儲(chǔ)的時(shí)候是從Box[1]開(kāi)始存儲(chǔ)的础废，Box[0]我們是不存東西的汛骂，Box[-1]更是會(huì)數(shù)組下標(biāo)越界，所以要加個(gè)約束條件评腺，也叫邊界條件帘瞭。而對(duì)于Box[1]，即到達(dá)第一個(gè)臺(tái)階的走法蒿讥，那只有一種可能蝶念，就是跨一步，所以Box[1] = 1; 對(duì)于Box[2]芋绸，即到達(dá)第2個(gè)臺(tái)階的走法媒殉，這時(shí)你可以一次一步上，也可以一次跨兩步上摔敛，所以有Box[2] = 2廷蓉。
因此有，
Box[6] = Box[5] + Box[4]
=(Box[4] + Box[3]) + (Box[3] + Box[2])
=((Box[3] + Box[2]) + (Box[2] + Box[1])) + ((Box[2] + Box[1]) + Box[2])
=((Box[2] + Box[1] + Box[2]) + (Box[2] + Box[1])) + ((Box[2] + Box[1]) + Box[2])
看到?jīng)]有马昙，所求的Box[6]最后都化成了我們已知的Box[1]和Box[2]的組合了桃犬。
但是，我們的代碼也要這么樣去拆分求解嗎行楞？NO,NO,NO攒暇，如果是這樣的話，那就還沒(méi)有領(lǐng)略到動(dòng)態(tài)規(guī)劃的美妙之處子房，哈哈形用，啥意思呢？既然你的問(wèn)題都可以用子問(wèn)題來(lái)求解池颈，那為什么我不把所有子問(wèn)題都求解好存起來(lái)尾序，這樣你一來(lái)求解，我就可以立馬返回給你你所需要的子問(wèn)題的解呢躯砰？
比如現(xiàn)在我們已知Box[1]和Box[2]每币，先把他們存起來(lái)，那Box[3]是不是就知道了（Box[3] = Box[2] + Box[1]）琢歇，再把Box[3]存起來(lái)兰怠，同理Box[4],Box[5],Box[6]也都可以求得了，并且都把他們存在Box中李茫，就像是金字塔一樣揭保，先從最小的子問(wèn)題慢慢往上推出父問(wèn)題的解，這樣一來(lái)魄宏，所有問(wèn)題都可以馬上取出它的解了秸侣。
好了，到此問(wèn)題講述的差不多了，其實(shí)如果大家理解了這個(gè)問(wèn)題味榛，那你就在不知不覺(jué)中開(kāi)始接觸了動(dòng)態(tài)規(guī)劃了椭坚，關(guān)于動(dòng)態(tài)規(guī)劃更詳細(xì)的介紹，我之后會(huì)整理一篇文章出來(lái)搏色，敬請(qǐng)期待善茎。
最后，附上上臺(tái)階問(wèn)題的完整代碼：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in)
int m = scan.nextInt();
int[] Box = new int[m + 1];//第0個(gè)位置舍棄不用频轿，從第一個(gè)位置開(kāi)始存
Box[1] = 1;//我們已知Box[1]和Box[2]垂涯，這也是邊界條件
Box[2] = 2;
for (int j = 2; j <= m; j++) {//依次計(jì)算并存儲(chǔ)每個(gè)問(wèn)題的解
Box[j] = Box[j - 1] + Box[j - 2];//這句是核心！
}
System.out.println(Box[m]);//Box[m]即走到m層的走法
}
}
