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!