思路1：最自然的思路應(yīng)該是窮舉思路要放棄志衣，新建一個(gè)數(shù)組用于儲(chǔ)存n從0到n-1的所有可能情況，對(duì)于n猛们，第一步只有兩種走法念脯，走一步或者走兩步，而a[n-1]和a[n-2]都是提前求好的弯淘，所以直接帶入求和即可
int climbStairs(int n){
if(n < 3)
return n;
int *a = (int *)malloc((n + 1)* sizeof(int));
a[0] = 0;
a[1] = 1;
a[2] = 2;
for(int i = 3; i <= n; i++){
a[i] = a[i-1] + a[i-2];
}
return a[n];
}
思路2:對(duì)于思路1中的數(shù)組绿店，實(shí)際上我們只需要知道n之前的兩個(gè)數(shù)字就可以了，不需要記錄從0-n的所有數(shù)字庐橙，所以維護(hù)兩個(gè)變量就可以了假勿。
int climbStairs(int n){
if(n < 3)
return n;
int first = 1;
int second = 2;
int result = 0;
for(int i = 3; i <= n; i++){
result = first + second;
first = second;
second = result;
}
return result;
}
思路3:對(duì)于要記錄的兩個(gè)數(shù)，實(shí)際上可以直接遞歸,可惜提交的時(shí)候會(huì)報(bào)超時(shí) saaaaaad
int climbStairs(int n){
if(n < 3)
return n;
return climbStairs(n-1) + climbStairs(n-2);
}
本系列文章态鳖，旨在打造LeetCode題目解題方法转培，幫助和引導(dǎo)同學(xué)們開(kāi)闊學(xué)習(xí)算法思路，由于個(gè)人能力和精力的局限性浆竭，也會(huì)參考其他網(wǎng)站的代碼和思路堡距，如有侵權(quán)，請(qǐng)聯(lián)系本人刪除兆蕉。
