I am not able to solve Speculating on Buffaloes for quite some time and it is driving me mad. Can someone please explain the dp recurrence to me?
This is fairly standard problem on buying and selling stocks.
Here, we can do at most k/2 transactions (A transaction is a buy and sell operation together).
So let’s do k /= 2
Here’s a simple O(n* k * k) solution
Let DP[i][j] be the max profit possible till day i and using at most j transactions.
The transition will be - for a day i at transaction t we go through all previous days j ( j < i ) and see if we bought buffalo at j and sell at day i what profit we made.
This profit will be = ( DP[j][t-1] + (price[i] - price[j] ) )
Keep track of this to find max profit.
Also we may not do any transaction at i so we can also max with previous DP[i][t-1].
1 Like
Speculating on Buffaloes (and many of its variants) is DP problem.
But, If you check out the IARCS study material, you’ll find out that the question is listed under greedy algorithm. And they even have provided a greedy strategy to solve it. IDK if it’s wrong or right (I’m a newbie), but maybe you can see their solution and see if the greedy strategy works or not.
Link: https://www.iarcs.org.in/inoi/online-study-material/problems/buffalos.php
1 Like
That is a different problem. See the problem statements of both the problems carefully
2 Likes
oh yes. I saw the difference. Thanks!