遞推、回溯。

爬樓梯問題，每次可以走1步或者2步，爬上n層樓梯的總方法。

（是不是你見過的最短的題目描述了，除了a+b）

    能進(jìn)則進(jìn)，不進(jìn)則退。（回溯法八字真言）

• 輸入n

• 設(shè)地面為第0層

• 利用遞歸求解

• 參數(shù)每次加1或加2

• 參數(shù)等于n，答案加1并返回

• 參數(shù)大于n，及時返回

• 直到模擬完所有可能

• 輸出答案

#include<cstdio>

int n,ans = 0; //n樓梯總數(shù) ans當(dāng)前方案數(shù)

void dfs(int i) { //當(dāng)前在第i層樓梯上

    if(i == n){ //走到第n層

       ans++;//方案數(shù)加1

       return;//及時返回

    }

    if(i >n) { //超過n層

       return;//及時返回

    }

    dfs(i+1);//走一層

    dfs(i+2);//走兩層

    return;

}

int main() {

    scanf('%d',&n);

    dfs(0); //從地面開始走

    printf('%d\n',ans);

    return 0;

}

【洛谷 P1255】https://www./problemnew/lists?name=1255

1. 如果每次都可以爬1級、2級或3級，你會修改嗎？
   

2. 如果是每次可以選擇m級呢？（m <= n）

3. 上面給出的例題，按照遞歸算法只可以通過50%的數(shù)據(jù)，在下一篇文章里會為大家介紹更為高效的遞推算法，你可以獨立想出來遞推公式嗎？