CODEWITHSUNDEEP
javaalgorithmdynamic-programming
Htlcs
Htlcs

Reputation: 555

understanding the flow of a simple dynamic programming

I just started understanding the concept of dynamic programming. I understand it is used to cache results for future calls and its really efficient in designing complex algorithms that give an exponential runtime. What I don't understand is how the flow would work programmatically. For example to calculate the nth Fibonacci number using dynamic programming as follows. What is the flow like in the program?

int[] fibMap = new int[max]
int fibo(int i){
  if(i == 0) return 0;
  if(i == 1) return 1;
  if( fibMap[i] != 0) return fibMap[i]; // return cached result
  fibMap[i] = fibo(i-1)+fibo(i-2);      //Cache result
  return fibMap[i];
}

I found this code from one of the Java reference books that I am using but I am having hard time figuring out how this program would work. Say if we would want to calculate a simple fibo(3) or fibo(5), could someone please explain me how the program would cache result and how the overall flow would work for this problem compared to a normal recursive approach without DP like below?

int fibo(int i){
   if(i == 0) return 0;
   if( i == 1) return 1;
   return fibo(i-1) + fibo(i-2);
}

Upvotes: 0

Views: 112

Answers (1)

user541686
user541686

Reputation: 210402

Your code is

int fibo(int i){
  if(i == 0) return 0;
  if(i == 1) return 1;
  if( fibMap[i] != 0) return fibMap[i]; // return cached result
  fibMap[i] = fibo(i-1)+fibo(i-2);      //Cache result
  return fibMap[i];
}

or, equivalently

int fibo(int i){
  if(i == 0) return 0;
  if(i == 1) return 1;
  if( fibMap[i] == 0)
    fibMap[i] = fibo(i-1)+fibo(i-2);      //Cache result
  return fibMap[i];
}

so the "flow" is basically exactly the same thing as the non-cached version, except that you avoid recalculating results you've already computed.

Upvotes: 2

Related Questions