Yukicoder044 DPなすごろく

問題概要

地点0から地点$N$まで移動する。移動方法は1歩進む、2歩進むのいずれかである。 到達するパターンは何パターンあるか。

$N\leqq50$

yukicoder044

解法

状態の遷移がとてもわかり易い。 あるマスへの到達は、1,2歩前からのみ。 $dp(i):=i$にたどり着くまでの組み合わせ で解ける。

あとからFibonacci数であることに気がついた。 小さいNに対するFibonacci数は適当に計算できる。

計算量:$O(N)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VL = vector<LL>;        using VVL = vector<VL>;
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    
    LL N;
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        VL dp(N + 1, 0);
        dp[0] = dp[1] = 1;
        FOR(i, 2, N + 1) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        ans = dp[N];
        cout << ans << "\n";
    
        return 0;
    }