**Introduction**↵
↵
Dynamic Programming (DP) is a powerful tool in competitive programming, but it can be tricky to master. In this blog, we’ll go through 5 essential DP tricks that can make even the hardest problems manageable. Each trick comes with a clear example and a Codeforces problem so you can practice immediately.↵
↵
1-Prefix and Suffix DP↵
======================↵
Avoid recalculating the same subproblems by maintaining prefix or suffix arrays.↵
↵
Example: Calculate sum of any subarray in O(1) using prefix sums.↵
↵
~~~~~↵
vector<int> prefix(n+1, 0);↵
for(int i = 0; i < n; i++) {↵
prefix[i+1] = prefix[i] + arr[i];↵
}↵
int sum = prefix[r+1] - prefix[l]; // sum of subarray [l, r]↵
~~~~~↵
↵
Tip: Precompute cumulative results to reduce repetitive calculations.↵
↵
2-DP on Trees↵
=============↵
When working with trees, standard DP often fails. Use DFS + DP to store subtree results.↵
↵
~~~~~↵
void dfs(int u, int parent) {↵
dp[u] = value[u];↵
for(int v : adj[u]) if(v != parent) {↵
dfs(v, u);↵
dp[u] += max(0, dp[v]);↵
}↵
}↵
~~~~~↵
↵
Pro Tip: Decide if you need downward or upward DP values.↵
↵
3-Bitmask DP↵
==============↵
Useful for subset problems (like TSP). Represent subsets as integers and store the optimal solution.↵
↵
~~~~~↵
for(int mask = 0; mask < (1<<n); mask++) {↵
for(int i = 0; i < n; i++) if(!(mask & (1<<i))) {↵
DP[mask | (1<<i)] = min(DP[mask | (1<<i)], DP[mask] + cost[i]);↵
}↵
}↵
~~~~~↵
↵
4-Space Optimization↵
====================↵
Reduce O(n²) DP space to O(n) by keeping only the previous row.↵
↵
~~~~~↵
vector<int> prev(n+1, 0), curr(n+1, 0);↵
for(int i = 1; i <= n; i++) {↵
for(int j = 1; j <= n; j++) {↵
curr[j] = max(prev[j], prev[j-1] + arr[i]);↵
}↵
prev = curr;↵
}↵
~~~~~↵
↵
5-Sliding Window / Monotonic Queue DP↵
=======================================↵
When DP depends on the previous k states, use a sliding window or monotonic queue to optimize.↵
↵
~~~~~↵
deque<int> q;↵
for(int i = 0; i < n; i++) {↵
while(!q.empty() && q.front() < i-k) q.pop_front();↵
dp[i] = dp[q.front()] + arr[i];↵
while(!q.empty() && dp[i] > dp[q.back()]) q.pop_back();↵
q.push_back(i);↵
}↵
~~~~~↵
↵
Conclusion↵
----------↵
Mastering these 5 DP tricks will make you faster and more confident in contests. Don’t just read—practice! Try thelinked problems and implement the solutions without peeking.↵
↵
_**Challenge:**_ Can you combine Bitmask DP with Tree DP? ↵
Try it in your next contest and share your results in the comments!
↵
Dynamic Programming (DP) is a powerful tool in competitive programming, but it can be tricky to master. In this blog, we’ll go through 5 essential DP tricks that can make even the hardest problems manageable. Each trick comes with a clear example and a Codeforces problem so you can practice immediately.↵
↵
1-Prefix and Suffix DP↵
======================↵
Avoid recalculating the same subproblems by maintaining prefix or suffix arrays.↵
↵
Example: Calculate sum of any subarray in O(1) using prefix sums.↵
↵
~~~~~↵
vector<int> prefix(n+1, 0);↵
for(int i = 0; i < n; i++) {↵
prefix[i+1] = prefix[i] + arr[i];↵
}↵
int sum = prefix[r+1] - prefix[l]; // sum of subarray [l, r]↵
~~~~~↵
↵
Tip: Precompute cumulative results to reduce repetitive calculations.↵
↵
2-DP on Trees↵
=============↵
When working with trees, standard DP often fails. Use DFS + DP to store subtree results.↵
↵
~~~~~↵
void dfs(int u, int parent) {↵
dp[u] = value[u];↵
for(int v : adj[u]) if(v != parent) {↵
dfs(v, u);↵
dp[u] += max(0, dp[v]);↵
}↵
}↵
~~~~~↵
↵
Pro Tip: Decide if you need downward or upward DP values.↵
↵
3-Bitmask DP↵
==============↵
Useful for subset problems (like TSP). Represent subsets as integers and store the optimal solution.↵
↵
~~~~~↵
for(int mask = 0; mask < (1<<n); mask++) {↵
for(int i = 0; i < n; i++) if(!(mask & (1<<i))) {↵
DP[mask | (1<<i)] = min(DP[mask | (1<<i)], DP[mask] + cost[i]);↵
}↵
}↵
~~~~~↵
↵
4-Space Optimization↵
====================↵
Reduce O(n²) DP space to O(n) by keeping only the previous row.↵
↵
~~~~~↵
vector<int> prev(n+1, 0), curr(n+1, 0);↵
for(int i = 1; i <= n; i++) {↵
for(int j = 1; j <= n; j++) {↵
curr[j] = max(prev[j], prev[j-1] + arr[i]);↵
}↵
prev = curr;↵
}↵
~~~~~↵
↵
5-Sliding Window / Monotonic Queue DP↵
=======================================↵
When DP depends on the previous k states, use a sliding window or monotonic queue to optimize.↵
↵
~~~~~↵
deque<int> q;↵
for(int i = 0; i < n; i++) {↵
while(!q.empty() && q.front() < i-k) q.pop_front();↵
dp[i] = dp[q.front()] + arr[i];↵
while(!q.empty() && dp[i] > dp[q.back()]) q.pop_back();↵
q.push_back(i);↵
}↵
~~~~~↵
↵
Conclusion↵
----------↵
Mastering these 5 DP tricks will make you faster and more confident in contests. Don’t just read—practice! Try the
↵
_**Challenge:**_ Can you combine Bitmask DP with Tree DP? ↵
Try it in your next contest and share your results in the comments!
