### Jamshed11's blog

By Jamshed11, 2 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 = 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 = 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.assign(k + 1, 0);
dp = 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. Comments (4)
 » Nice explanation !
 » 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[MaxK]; //Filling answers for initial states dp = 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]; } } 
•  » » wow so useful Ò.ó
 » 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$)