京都大学の過去問 [yukicoder No.786]

https://yukicoder.me/problems/no/786

前提知識

• 動的計画法（組み合わせ系）

解説

https://yukicoder.me/submissions/315631

dpで解く。
dp[i] := i段目に到達するまでの登り方の組み合わせ数
すると、遷移は
dp[i + 1] += dp[i] // 1歩で1段
dp[i + 2] += dp[i] // 1歩で2段
となり、dp[N]が答え。
　
mod10^9+7も出てこないので、組み合わせDP初級としていいかも

int N;
ll dp[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    dp[0] = 1;
    rep(i, 0, N) {
        dp[i + 1] += dp[i];
        dp[i + 2] += dp[i];
    }
    cout << dp[N] << endl;
}