📚 爬樓梯問題 🚀 題目瀏覽 【題目名稱】爬樓梯 【題目描述】

樹老師爬樓梯，他可以每次走 1 1 1 級(jí)或者 2 2 2 級(jí)，輸入樓梯的級(jí)數(shù)，求不同的走法數(shù)。

為林口等地區(qū)用戶提供了全套網(wǎng)頁(yè)設(shè)計(jì)制作服務(wù)，及林口網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、林口網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！

例如：樓梯一共有 3 3 3 級(jí)，他可以每次都走一級(jí)，或者第一次走一級(jí)，第二次走兩級(jí)，也可以第一次走兩級(jí)，第二次走一級(jí)，一共 3 3 3 種方法。

【輸入】

輸入包含若干行，每行包含一個(gè)正整數(shù) N N N，代表樓梯級(jí)數(shù)， 1 ≤ N ≤ 30 1≤N≤30 1≤N≤30。

【輸出】

不同的走法數(shù)，每一行輸入對(duì)應(yīng)一行輸出。

【輸入樣例】

5
8
10

【輸出樣例】

8
34
89

【原題鏈接】

http://ybt.ssoier.cn:8088/problem_show.php?pid=1204

---

?? 題解分析

爬樓梯問題也是 遞推思想 的典型體現(xiàn)，這里把f[i]的方案看成了 一個(gè)集合，由「最后走 1 步的方案f[i-1]」和 「最后走 2 步的方案f[i-2]」這 兩個(gè)子集合 構(gòu)成，做到了 不重復(fù)、不遺漏，因此只需按照方程f[i] = f[i-1] + f[i-2]去遞推即可。

【誤區(qū)提示??????】

此問題容易產(chǎn)生的一個(gè)誤區(qū)，就是把方程書寫成f[i] = f[i-1] + 2*f[i-2]。

這是因?yàn)樵诳紤]問題時(shí)，把「最后一步走幾步」? 誤解成了「最后走幾步有多少種方案」?

這就導(dǎo)致在考慮f[i-2]時(shí)，認(rèn)為 最后走 2 步有 2 種方案，把f[i-2] 與 f[2]產(chǎn)生了聯(lián)系，所以在f[i-2]前乘了 2。?

仔細(xì)思考，我們會(huì)發(fā)現(xiàn)上面這種思想，本質(zhì)上導(dǎo)致兩個(gè)子集出現(xiàn)了重復(fù)，因?yàn)?「最后走 2 步中，每次走 1 步」的方案，其實(shí)是包含在 「最后走 1 步」中的，所以產(chǎn)生了錯(cuò)誤。

也就是說，「f[i-2]與f[2]是沒有關(guān)系的」??

初學(xué)者在初學(xué)時(shí)犯了這種錯(cuò)誤后，需要仔細(xì)思考原因，避免下次再走入這個(gè)誤區(qū)。🍀

---

🧑🏻?💻 C++ 代碼

#includeusing namespace std;

typedef long long ll;
const int N = 35;
int tmp;
int f[N];

int main() {
    ios::sync_with_stdio(false);  //cin讀入優(yōu)化
    cin.tie(0);

    f[1] = 1;
    f[2] = 2;
    for (int i = 3; i< N; ++i) {
        f[i] = f[i - 1] + f[i - 2];  //最后走1步的方案 + 最后走2步的方案
    }

    while (cin >>tmp) {
        cout<< f[tmp]<< endl;
    }

    return 0;
}

---

?? 寫在最后

如果各位小伙伴覺得博主的題解寫的不錯(cuò)，可以給本文 點(diǎn)個(gè)贊 👍

這樣可以讓 更加優(yōu)質(zhì)的文章 有 更大的概率 被推送到 搜索界面的榜首，為未來的小伙伴們節(jié)約更多搜索、閱讀的成本。 🚀

同時(shí)，你的支持 也是我 不斷創(chuàng)作 的動(dòng)力。??

有想要看更多題解報(bào)告的小伙伴，也可以關(guān)注我的專欄「信息奧賽題解」。

我們下期再見。👋

---

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：【信息奧賽題解】爬樓梯（詳細(xì)題解&C++代碼）-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)網(wǎng)址：http://weahome.cn/article/cojepi.html