State Representation & State-Space Compression
Designing the right DP or graph state representation—minimizing redundant dimensions, encoding subsets as bitmasks, and using rolling arrays—is the key to turning slow exponential ideas into fast polynomial solutions.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
State Representation & State-Space Compression
Every Dynamic Programming and State-Space Shortest Path solution is defined by its state: the minimal information needed from past decisions to make optimal future decisions (Markov property).
4 Rules of Great State Design
1. Drop Derivable Dimensions: If j is uniquely determined by other state variables (e.g., worker = popcount(mask) in Bitmask DP, or j = steps - i in two-walker grid DP), remove j to cut state space by $O(n)$!
2. Swap Value & Index: When capacity $W \le 10^9$ is huge but total value $V \le 10^5$ is small, make value the state index and store minWeight[value] as the DP value!
3. Rolling Array Compression: If dp[i] depends only on dp[i - 1], replace a 2D table with two 1D rows (or one backward-looped row in 0/1 Knapsack).
4. Add Small Auxiliary Flags: Adding a tiny boolean/enum dimension (like holdingStock ∈ {0, 1} or couponUsed ∈ {0, 1}) cleanly captures constraints without blowing up complexity!
---
Example: Stock Trading with Cooldown (Finite State Machine DP, LeetCode 309)
Model daily states as 3 variables: hold (own stock), sold (just sold today → cooldown tomorrow), and rest (free to buy). Time: $O(n)$. Space: $O(1)$!
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
int maxProfitCooldown(const std::vector<int>& prices) {
int hold = INT_MIN / 2, sold = 0, rest = 0;
for (int p : prices) {
int prevSold = sold;
sold = hold + p;
hold = std::max(hold, rest - p);
rest = std::max(rest, prevSold);
}
return std::max(sold, rest);
}
int main() {
std::cout << maxProfitCooldown({1, 2, 3, 0, 2}) << "\n"; // buy 1, sell 3, cooldown 0, buy 0, sell 2 -> 3
return 0;
}
</details>
---
Related Topics
- Bitmask DP, Digit DP, and Problem Modeling.