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 the 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!