jeudi 7 décembre 2017

Cant understand how dynamic programming works : Wine selection

Here's the problem statement: Selecting Wine Dynamic Programming

Here's the code:

int N; // read-only number of wines in the beginning
int p[N]; // read-only array of wine prices
int cache[N][N]; // all values initialized to -1 (or anything you choose)

    int profit(int be, int en) {
      if (be > en)
        return 0;

     // these two lines save the day
      if (cache[be][en] != -1)
        return cache[be][en];                 //line l1


      // when calculating the new answer, don't forget to cache it
      return cache[be][en] = max(             //line l2
        profit(be+1, en) + year * p[be],
        profit(be, en-1) + year * p[en]);
    }

  • Lets say cache[be][en] is assigned value x in recursion r1(line l2 is executed).

  • Now , when i move on to next recursion r2 , line l1 is executed and cache value is returned.

I cant find how cache value is updated as we move from recursion r1 to recursion r2.

Can i get a good explanation of how this code works ?

Aucun commentaire:

Enregistrer un commentaire