Advertisement
Josif_tepe

Untitled

Mar 18th, 2021
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.88 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int memo[1005];
  6. int fib(int x) {
  7.     if(x == 1) {
  8.         return 1;
  9.     }
  10.     if(x == 2) {
  11.         return 1;
  12.     }
  13.     if(memo[x] != -1) {
  14.         return memo[x];
  15.     }
  16.     memo[x] = fib(x - 1) + fib(x - 2);
  17.     return memo[x];
  18. }
  19. int main()
  20. {
  21.     int n;
  22.     cin >> n;
  23.     for(int i = 1; i <= n; i++) {
  24.         memo[i] = -1;
  25.         // -1 znaci deka ne e presmetano
  26.         // se sto e razlicno od -1 znaci deka ni e presmetano
  27.        
  28.     }
  29.     cout << fib(n) << endl;
  30.     return 0;
  31. }
  32. // fib(7) --> fib(6) + fib(5) = 8 + 5 = 13 memo[7] = 13
  33. // fib(6) --> fib(5) + fib(4) = 5 + 3 = 8 memo[6] = 8
  34. // fib(5) --> fib(4) + fib(3) = 3 + 2 = 5 memo[5] = 5
  35. // fib(4) --> fib(3) + fib(2) = 2 + 1 = 3 memo[4] = 3
  36. // fib(3) --> fib(2) + fib(1) = 1 + 1 = 2  memo[3] = 2
  37. // fib(2) --> 1 memo[2] = 1
  38. // fib(1) --> 1 memo[1] = 1;
  39.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement