aoj

ALDS1_10_A Fibonacci Number

ALDS1_10_A Fibonacci Number
Feb. 2, 2020, 1:52 p.m.

目次

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
int fib(vector<int> &dp, int n) {
    if (n == 0 || n == 1) {
        return dp[n] = 1;
    }

    if (dp[n] > 0) return dp[n];

    return dp[n] = fib(dp, n - 1) + fib(dp, n - 2);
}


int main(void){
    int n;
    cin >> n;
    vector<int> dp(n+1);
    cout << fib(dp, n) << endl;
}