Dynamic programming

Joined
Jan 9, 2023
Messages
1
Reaction score
0
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:
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;
}
 
Joined
Sep 21, 2022
Messages
120
Reaction score
15
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
Code:
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
 
Joined
Dec 21, 2022
Messages
28
Reaction score
4
Not sure what are you trying to achieve....

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

C++:
// 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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,754
Messages
2,569,516
Members
44,991
Latest member
Josephnag

Latest Threads

Top