- Joined
- Jan 9, 2023

- Messages
- 1

- Reaction score
- 0

Yesterday i got a problem to solve in which i had to use recurrence. I solved this problem, but for big input data my program is slow.

My teacher said that if i want to get 100%, i need to use dynamic programming, but i am newbie to dp. I solved 2, max 3 problems using dp and i am not able to come up with algorithm, which would use memoization.

In task i need to find number of ways n can be represented using sum of at least 2 fibonacci numbers, where fib = {1, 2, 3, 5...}. You cannot use more than one same number in one representation, eg if input is 10, output should be 2, 'cause 10 = 8 + 2 = 5 + 3 + 2.

If you can help, please do it, thanks for all comments in advance.

my code:

C++:

```
#include <bits/stdc++.h>
using namespace std;
void genLicFib(int n);
int roz(int n, int ind);
vector <int> fib = {1, 2};
int main() {
int n;
cin >> n;
genLicFib(n);
cout << roz(n, fib.size() - 1);
}
void genLicFib(int n) {
while (fib.back() < n)
fib.push_back(fib.back() + fib[fib.size() - 2]);
fib.pop_back();
}
int roz(int n, int ind) {
if (n == 0)
return 1;
int sum = 0;
for (int i = ind; i >= 0; i --) {
if (fib[i] > n)
continue;
sum += roz(n - fib[i], i - 1);
}
return sum;
}
```