Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int memo[1005];
- int fib(int x) {
- if(x == 1) {
- return 1;
- }
- if(x == 2) {
- return 1;
- }
- if(memo[x] != -1) {
- return memo[x];
- }
- memo[x] = fib(x - 1) + fib(x - 2);
- return memo[x];
- }
- int main()
- {
- int n;
- cin >> n;
- for(int i = 1; i <= n; i++) {
- memo[i] = -1;
- // -1 znaci deka ne e presmetano
- // se sto e razlicno od -1 znaci deka ni e presmetano
- }
- cout << fib(n) << endl;
- return 0;
- }
- // fib(7) --> fib(6) + fib(5) = 8 + 5 = 13 memo[7] = 13
- // fib(6) --> fib(5) + fib(4) = 5 + 3 = 8 memo[6] = 8
- // fib(5) --> fib(4) + fib(3) = 3 + 2 = 5 memo[5] = 5
- // fib(4) --> fib(3) + fib(2) = 2 + 1 = 3 memo[4] = 3
- // fib(3) --> fib(2) + fib(1) = 1 + 1 = 2 memo[3] = 2
- // fib(2) --> 1 memo[2] = 1
- // fib(1) --> 1 memo[1] = 1;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement