可將此題可想像成一維矩陣填色問題

踩一階是填入長度為1的正方形 踩兩階是填入長度為2的長方形

由此可知每兩格都可以獨立成一個區塊 所以若前面已經填入兩格 則下一格的排列數量為上一格及上上格的排列數量加總

因此狀態轉移式可以寫成 dp[i] = dp[i-1] + dp[i-2] --> dp 陣列紀錄幾階會有幾種排列

用迴圈依序為陣列填入值並回傳dp[n]即為答案

此題本質上就是費氏數列

AC解答⬇️

#include <iostream>

using namespace std;

int main() {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    int n;

    long long dp[105]={1,1,2};

    while (cin >> n) {

        for (int i = 3; i <= n; i++)

            dp[i] = dp[i-1]+dp[i-2];

        cout << dp[n] << "\n";

    }

    return 0;

}