witam, zabralem sie dzisiaj za problem wyznaczenia ilosci unikatowych rozkladow liczby na liczby fibonacciego (tzn. np dla liczby 10 bedzie odp: 2, poniewaz 10 = 8 + 2 = 5 + 3 + 2).
zauwazylem, ze w tym zadaniu (podobnie jak w algorytmie wydawania reszty) trzeba bedzie zastosowac programowanie dynamiczne. niestety rozwiazanie to daje mi 59% (dwa testy daja bledna odp. w tym przypadku obydwa bledy brzmia: wczytano '2' a oczekiwano '1').
pomozecie okreslic gdzie lezy blad w mojej implementacji algorytmu?
dodam rowniez, ze dla jednego testu mam przekroczenie limitu czasu (a to oznacza, ze prawdopodobnie bede musial utworzyc tablice sum prefiksowych liczb fibonacciego i zamiast naiwnie szukac liczby fibonacciego mniejszej od liczby, ktora chce rozlozyc, bede musial wyszukiwac binarnie taka liczbe)
zadanie: link
wyniki: link
kod:
#include <bits/stdc++.h>
using namespace std;
void genLicFib(int n);
int roz(int n, int ind);
vector <int> fib;
int main() {
int n;
cin >> n;
genLicFib(n);
cout << roz(n, fib.size() - 1);
}
void genLicFib(int n) {
fib.push_back(1);
fib.push_back(2);
while (fib.back() < n)
fib.push_back(fib.back() + fib[fib.size() - 2]);
}
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;
}