假設(shè)你正在爬樓梯聋伦。需要 n階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺階冤灾。你有多少種不同的方法可以爬到樓頂呢玛臂？
注意：給定 n 是一個(gè)正整數(shù)隙轻。
image
思路：
前期分析：
動(dòng)態(tài)規(guī)劃：將一個(gè)大問題劃分為若干個(gè)子問題，先求解子問題垢揩，然后就合并解決大問題。 子問題之間是有關(guān)系的敛瓷，即不是獨(dú)立的子問題叁巨，這個(gè)就是和分治法的區(qū)別，分治法是獨(dú)立的呐籽。
動(dòng)態(tài)規(guī)劃中锋勺，必須保證重復(fù)子問題只運(yùn)行一次，所以就需要空間來記錄狡蝶。一般用 迭代庶橱。而分治法 一般用 遞歸。
具體問題分析：
將這個(gè)爬完這個(gè)n層的樓梯贪惹，分解苏章。設(shè)想，怎么樣才能在最后的時(shí)候一次到達(dá)第n層奏瞬，這時(shí)就是枫绅，在n-1層（接下來走1步），或者n-2層（接下來走2步）硼端。即最后想要到達(dá)的最后一層的時(shí)候并淋，最后一步，必需是在n-1珍昨，或者n-2層县耽，兩種情況。
如何到達(dá)n-1層镣典？就用上面的思路兔毙，最后一步在 （n-1）- 1層或者 （n-1）-2層
··········
直到1，0層骆撇；
我們會(huì)發(fā)現(xiàn) 這個(gè)就是 斐波拉瞒御！
int climbStairs(int n) {
int a = 1,b = 1,c = 1;
if(n == 0 || n== 1){
return c;
}
for( int i = 0;i<n-1;i++){
c = a+b;
a = b;
b = c;
}
return c;
}
