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