(C++) - 백준(BOJ) 2748번 : 피보나치 수 2

https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

대표적인 dp문제였습니다.

 

 

Code

1. Top down dp

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll fibo[91], n;
ll dp(int num){
    if(num == 1 || num == 2) return 1;
    ll &ret = fibo[num];
    if(ret) return ret;
    ret = 0;
    return ret = dp(num - 1) + dp(num - 2);
}

int main(){
    cin >> n;
    cout << dp(n);
}

 

2. bottom up dp

#include <iostream>
using namespace std;
int main(){
int num;
cin >> num; //방 개수
long long *arr = new long long[num+1];
if(num == 0 ||num == 1)
{
cout<< num;
return 0;
}
arr[0] = 0;
arr[1] = 1;
for(int i = 2; i<=num; i++)
{
arr[i] = arr[i-2] + arr[i-1];
}
cout<<arr[num];
}