CODEWITHSUNDEEP
algorithm
userssss1
userssss1

Reputation: 31

Solving recurrence relation when N is very big

How to solve recurrence relation when 0 <= N <= 1,000,000,000 ?.

For example, 

like  d[N] = d[N-1] + d[N-2] * 3d[N-3]

I try to solve problem using DP and memorization, but N range is too big to making array. The input N is random.

Is there another algorithm that I can get to the problem?.

Upvotes: 0

Views: 61

Answers (1)

nice_dev
nice_dev

Reputation: 17805

You only need to remember 3 previous values. So make an array of size 3 and overwrite each one in to the other for further processing.

int[] memo = new int[3];

// some initializations etc

for(....){
    int new_value = memo[2] + memo[1] * 3 * memo[0];
          memo[0] = memo[1];
          memo[1] = memo[2];
          memo[2] = new_value;
}

// further processing

Upvotes: 2

Related Questions