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));
//Filling answers for initial states
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);
//Filling answers for initial states
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);
//Filling answers for initial states
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.
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:
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$$$)