I am trying to solve this problem:
https://www.codechef.com/problems/DBOY
and I have come up with the following recurrence which apparently seems to work for many tests I tried manually.
ll dp(int rem_fuel, int item)
{
if(rem_fuel == 0)
return 0;
if(item > n || rem_fuel < 0)
return 1e9;
if(k[item] > rem_fuel)
{
dp(rem_fuel, item+1);
}
return min((rem_fuel/k[item] + dp((rem_fuel%k[item]), item+1)), dp(rem_fuel, item+1));
}
This gives a TLE(quite obvious) although I am not sure how should I proceed thinking about memoizing this? I did try storing the states in mem[rem_fuel][item] but I believe the states get overwritten somewhere in the tree. Is it even possible to memoize such a recurrence? I would be grateful for any help. Thanks in advance!