Dynamic programming

[polandonion]

Hey,
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:

#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;
}

 

[AngleWyrm]

 

[WhiteCube]

let F be the Fibonacci numbers
F(0)=1
F(1)=1
F(2)=2
F(3)=3

C(j,n) is the number of ways to partition n into unique Fibonacci numbers <= F(j)
C(0,0) = 1

recurrence relation:
C(j,n) = C(j-1,n-F(j)) + C(j-1,n)

if j<0 or n<0 then C(j,n) = 0

pseudocode

mainline:
  select the largest j such that F(j)<n
  initialise an array (all -1) to be used by function C
  array[0][0] = 1
  PRINT C(j,n)
  END
 
FUNCTION C(j,n)
 IF j<0 OR n<0 THEN
  r = 0
 ELSE
  IF array[j][n]  == -1 THEN
   array[j][n] = C(j-1,n-F(j)) + C(j-1,n)
  END IF
  r = array[j][n]
 END IF
 RETURN r
END FUNCTION

 

[tea-age.solutions]

Not sure what are you trying to achieve....

There are 2 major ways in solving those problems: recursively and iteratively.

// recursive
long long fib( long long x ) noexcept
{
    if( x == 0 || x == 1 ) {
        return x;
    } else {
        return fib( x - 1 ) + fib( x - 2 );
    }
}

// iterative
long long fib_loop( long long x ) noexcept
{
    if( x < 1 ) { return 0; }
   
    long long  out  = 1;
    long long  prev = 0;

    for( long long i = 2; i <= x; ++i ) {
        auto tmp = out;
        out += prev;
        prev = tmp;
    }

    return out;
}

Do you want build a lookup table with the vector?
If yes, you should do that at compile time.
Or even better: provide a constexpr function, which can be used at compile time and runtime.
Your current approach will be very slow. It could only be considered if you need to calculate fibonacci very very often in a row, where the vector is only build once. Although the compile time variant will be way more better anyway.