Obliczenie zadanej liczby z ciągu fibonacciego - programowanie dynamiczne

Witam, dzis postanowilem zrobic pierwsze zadanie w zyciu na uzycie dp. Nauczyciel polecil mi: to zadanie. Zrobilem je, ale nie daje mi 100%, ze wzgledu na czas. Powie ktos w jaki sposob uzyc tutaj memoizacji / cachowania? A moze po prostu wystarczy wektor sum prefiksowych liczb fibonacciego? Prosilbym o pomoc, z gory dzieki.

Wyniki:

Moj kod:

#include <bits/stdc++.h>

using namespace std;

void genLicFib(int n);
int roz(int n, int ind);

vector <int> fib = {1, 2};
//vector <int> fibSuf = {1};
//int dp[1000001]; na razie nieprzydatna, bo nie robie memoizacji / cachowania

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(); // suma ma miec minimum 2 czynniki, wiec jesli n jest liczba fibonacciego,
					// to bede liczyl o jedno za duzo. Taki manewr rozwiazuje ten problem.

	/* while (fibSuf.back() < n)
		fibSuf.push_back(fibSuf.back() + fib[fibSuf.size()]);
    fibSuf.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;
}

Przecież ty w ogóle tutaj nie używasz programowania dynamicznego - ta tablica db to pic jest. Napisz rozwiązanie liniowe które korzysta z tablicy db i zmieścisz się w czasie.

enedil napisał(a):

Przecież ty w ogóle tutaj nie używasz programowania dynamicznego - ta tablica db to pic jest. Napisz rozwiązanie liniowe które korzysta z tablicy db i zmieścisz się w czasie.

wlasnie nie wiem jak uzyc programowania dynamicznego

Nie doczytałem zadania :/

weź wpisz w google fibonaci cache cpp. Temat oklepany jak habeta po westernie. Są tam dokładne wytłumaczenia. Też nie docztałem.

To wariacja problemu plecakowego. https://platform.meetit.pl/articles/dyn_ple Musisz zmienić rozwiązanie problemu sumy prezentowane na tej stronie. Twój podzbiór liczb z których składasz N to liczby fibbonaciego, a ty zamiast sprawdzic czy daną liczbę da się utworzyć musisz policzyć liczbę kombinacji.