In this question, I am thinking of dp state as solve(i,a,b ) where I am at the ith position with a and b as defined in the question, now I have 2 options: either to include guddu’s bullets or to include babu’s bullets, if I select 1st option I am reducing a by 1, similarly for 2 I’m reducing b by 1 and calling for the i-1 state. What’s wrong in my approach?
Maximum Bullets using DP
@Vishal_234
Your approach seems to be correct, you may have done some mistake in implementing it.
Maybe something in base cases or using int instead of long long.
Have a look at my code, i have implemented the exact same logic https://ide.codingblocks.com/s/249740
Please also mark the doubt as resolved if you are able to solve it now.
Why are we storing only dp[i][a] and not dp[i][a][b] ?
@Vishal_234
see there if we you 3d DP, then the space complexity will be (5000 )^3 which is more than 10^8 so it will give Runtime error.
So we can optimize it using just 2 parameters.
We are able to reduce it to 2 because among a and b overall only one of them is responsible for defining the state of dp so if we know one of them then we can find other.
For eg:-
supose initially a=3 , b=4, n=5
now for current state i=3, and b’=2 which means (b’ = b-2 = 4-2) so 2 items are taken by guddu bhaiya but since i=3 that means i=0,1,2 i.e. 3 boxes are already taken. So one box is taken by bablu
so accordingly a’ should be a’ = a-1 = 3-1 = 2.
So here there are only 2 unique parameters that are defining the state of DP.
This is a nice optimization and observation which you can use many times.
I hope you have understood it, please mark the doubt as resolved if you have understood it.
1 Like
Thank you so much.This observation and optimization would really help.