How to include dp table in Maximum Bullets?

#1

Sir I went through the hint video, but it does not seem to cover Dynamic Programming approach. Therefore I came up with recursive solution, but unaware of how to apply DP table to the solution.

#2

I think it has to a 2D dp rather than a single DP solution, the states of the DP are defined using the index and the number of bullets guddu/bablu has got.
You can check the code here.

1 Like
#3

Okay I referred the mentioned code, so with index i and ‘a’ shouldn’t we include b as well in the dp table?

#4

No, it’s not necessary, either by including a or including b will give you a unique state(how?, try dry running it once), moreover, we cannot make an array of size (5000 * 5000 * 5000).

1 Like
#5

Thanks, will look into it with dry run.