Let us first discuss a slightly inefficient approach which is more intuitive and then move to a optimized approach.

Let dp[i][j] be the number of gold coins to be used if prisoners in range [i,j] are considered.

So for every range [i,j], we iterate the number of prisoners in this range that need to be released.

For each such prisoner, we assume that this is the first prisoner to be released in the range,

and hence solve for further subproblems on either side of the removed prisoner.

Here is a bottom up implementation for the same : Solution

Complexity is

Time : O(P^{2}Q),

Memory : O(P^{2})

The key observation to reduce both Time and memory complexity is that we do not need to save every state, only states with dp[i][j] where i and j are a prisoner or a it’s neighbour or the edge(0 or P-1) matter, and hence we can use a top down approach along with a map, as mentioned in the editorial there to get the code to run optimally : Optimized Solution

Complexity is

Time : O(Q^{3}Log(Q^{3})),

Memory : O(Q^{2})

**Log is added due to map access