Jamshed11's blog

By Jamshed11, 10 months ago,

If you are someone who writes normal DP code first and then converts it to space optimized one, you can use this trick.

If our problem involves n * k states for DP, and at any point our state transition involves only moving from dp[i][x] to dp[i][y] or from dp[i][x] to dp[i + 1][y] i.e from i th layer to i th or i + 1 th layer, we can solve it in O(k) space.

But many times I first write code that uses O(n * k) space and then I optimize the space complexity. (It's easier for debugging)

Code that uses O(n * k) space looks something like this:

vector<vector<ll>> dp (n+1, vector<ll> (k+1));

dp[0][0] = 1;

for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < k; j++)
{
//State transitions from i th layer to i th or i + 1 th layer
dp[i][j+1] += dp[i][j];
dp[i+1][j+1] += dp[i][j];
}
}


E.g. 224168964

To convert this code to use O(k) space, I create 2 1-D vectors named dp and newDp and replace every occurrence of dp[i] with dp and every occurrence of dp[i+1] with newDp, and at the end of the first for loop I assign dp = newDp.

Code that uses O(k) space looks something like this:

vector<ll> dp (k+1);

dp[0] = 1;

for (ll i = 0; i < n; i++)
{
vector<ll> newDp (k+1);

for (ll j = 0; j < k; j++)
{
//State transitions from dp to dp or newDp
dp[j+1] += dp[j];
newDp[j+1] += dp[j];
}

dp = newDp;
}


E.g. 224028960

Instead of doing all these replacements I came up with a better idea.

The idea is my code will be very similar to the code that uses O(n * k) space. The only difference will be at the start of the i th layer I will assign memory to i + 1 th layer and when I am done with the i th layer I will release memory of i th layer i.e in the first for loop at the beginning I will do dp[i+1].assign(k + 1, 0); and at the end I will do dp[i].clear(); dp[i].shrink_to_fit();

Code that uses O(k) space using this trick looks something like this:

(It actually uses O(max(n, k)) space)

vector<vector<ll>> dp (n+1);

dp[0].assign(k + 1, 0);
dp[0][0] = 1;

for (ll i = 0; i < n; i++)
{
dp[i + 1].assign(k + 1, 0);

for (ll j = 0; j < k; j++)
{
//State transitions from i th layer to i th or i + 1 th layer
dp[i][j+1] += dp[i][j];
dp[i+1][j+1] += dp[i][j];
}

dp[i].clear();
dp[i].shrink_to_fit();
}


E.g. 224031624

Note: Only using dp[i].clear(); will still give you MLE as it only removes all elements from the vector but the underlying storage is not released. You need to use dp[i].shrink_to_fit(); to actually release the memory.

• +45

 » 10 months ago, # |   +5 Nice explanation !
 » 10 months ago, # |   +19 I've seen a lot of people using this approach, but I always prefer using a static array. It goes something like this: int dp[2][MaxK]; //Filling answers for initial states dp[0][0] = 1; bool cur = 0; for (ll i = 0; i < n; i++) { cur = !cur; for (ll j = 0; j <= k; j++) dp[cur][j] = 0; for (ll j = 0; j < k; j++) { //State transitions from dp to dp or newDp dp[!cur][j+1] += dp[!cur][j]; dp[cur][j+1] += dp[!cur][j]; } } 
•  » » 10 months ago, # ^ |   +6 wow so useful Ò.ó
 » 10 months ago, # |   +3 Instead, you can just write ($index$ & $1$), for ($index + 1$) parity changes. A bit general way, if you have a dependency of $dp[i]$ on $dp[i+1]$, $dp[i+2]$, ...., $dp[i+k-1]$, then you can simply write ($index$ % $k$)