I love dynamic programming and in Fall 2024, I joined the school ICPC team. This is a competition where teams of 3 work together to solve algorithm and data structure problems over 5 hours.

I was part of the second team.

As part of a team, it made sense for me to specialize in some topics. Thus, for the entire semester of Fall 2024, I focused exclusively on dynamic programming.

After spending an entire semester doing nothing but DP, I gained several insights into the essence of dynamic programming.

It’s really simple; It’s all just about STATE.

When first learning DP, you are probably taught about top down or bottom up.

When we do top down DP, we are thinking recursively. A property of recursion is that the call graph must not have cycles and there is a topological ordering to the function calls. In terms of state, recursion is just encoding the state through the function parameters of the recursive call.

Meanwhile, if you are thinking of DP from a bottom up perspective, your indexes are just shallow representation of the deeper concept of states. Since we know DP must have a topological ordering, bottom up DP is just about going through the vertices in a reverse topological ordering.

State, State, State, State, State

Index i, index j, index blah blah blah.

All that those numbers are doing is representing STATE. There is NO reason that state has to conform to the limitation of being represented by a few numbers.

When we do DP, we are not doing DP on some indexes, we are doing DP on some STATE.

The essence of DP is actually about state space search. DP is a search problem.

Let me repeat that: DP is a search problem.

You are just iterating over all the state once. That’s all DP is.

So if you figure out the states, you figure out the DP.

Let’s illustrate that with an example.

Example: Sushi

There are N plates with plate i having ai sushi. Taro picks a plate 1 to N with equal probability. If the chosen plate has sushi, Taro eats 1 sushi. If the chosen plate has no sushi, Taro does nothing.

What is the expected number times Taro would choose a plate until every plate is empty.

Input

1 ≤ N ≤ 300

1 ≤ ai ≤ 3

Idea

This problems boils down to how to encode the state efficiently. We could have N numbers with each number representing the number of sushi left on that particular plate. However, that would be an encoding with N dimensions, each dimension being one of four possible state (0, 1, 2, 3). The state space is thus, 4300. This is infeasible.

The insight then comes from finding the symmetry in the problem. In this case, the symmetry comes from the fact that every plate has equal probability of being chosen. So every plate with 3 sushi can be treated identically.

Mathematically, the picking a plate with x sushi transitions the state to 1 more plate of x-1 sushi, and 1 less plate of x sushi

// Let P(1 | state) be the probability of picking a plate with 1 sushi, P(2 | state) be plate with 2 sushi and so on.
dp[i][j][k] = P(1 | state) * dp[i-1][j][k] + P(2 | state) * dp[i+1][j-1][k] + P(3 | state) * dp[i][j+1][k-1] + P(0 | state)

Code

#include<bits/stdc++.h>
using namespace std;

double dp[301][301][301];
bool visited[301][301][301];

double dfs(int i, int j, int k, int n) {
    if (i < 0 || j < 0 || k < 0) {
        return 0;
    }
    if (visited[i][j][k]) {
        return dp[i][j][k];
    }
    double ans = 0;
    int cnt = i + j + k;

    ans += dfs(i-1, j, k, n) * (double) i;
    ans += dfs(i+1, j-1, k, n) * (double) j;
    ans += dfs(i, j+1, k-1, n) * (double) k;
    ans /= (double) cnt;
    ans += n / (double) cnt;
    visited[i][j][k] = true;
    dp[i][j][k] = ans;
    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &i : a) {
        cin >> i;
    }

    dp[0][0][0] = 0;
    memset(visited, false, sizeof(visited));
    visited[0][0][0] = true;

    vector<int> freq(4, 0);
    for (auto i : a) {
        freq[i]++;
    }

    cout << dfs(freq[1], freq[2], freq[3], n) << endl;
}

Mini Conclusion

The core of many dp problems is finding the smallest possible representation of state that still contains the necessary pieces of informations.

In this case, we took advantage of the symetry present to discard information about which specific plate has 1 sushi; We just needed to know the total number of plates with 1 sushi because every plate with 1 sushi behave identically.

Graph, Graph, Graph, Graph, Graph

“Every Problem is a Graph Problem” — some random team name

We know that DP is directed acyclic graph. We know this because that’s what a recursive function is.

Well, there are two things in a graph, vertices (state) and edges (transition / action).

We looked at state but that is a limiting. To see the other half of the picture, one must also understand that we are working with a graph. A graph with vertices and edges.

Internalize the idea of working backwards from the result. Ask yourself, “What is the last action the dp will take?”

Problem: Slimes

There are N slimes which can be merged with adjacent slimes. Each slime has a size of ai and the cost of merging two slimes is x + y where x is the cost of the left slime and y is the cost of the right slime.

What is the minimum cost to merge all N slime?

Input

2 ≤ N ≤ 400

1 ≤ ai ≤ 109

Idea

The “action” we do in this problem is merging. From that, we can see that we can use dp to solve the sub problem of optimal left and optimal right slime.

What are the possible states?

Ans: All possible ranges between 1 and 400, (ie, n2)

Code

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll dp[400][400];
ll prefix[400];
ll a[400];
bool visited[400][400];

ll range_sum(int l, int r) {
    if (l < 0) 
        return prefix[r];
    return prefix[r] - prefix[l];
}

ll solve(int i, int j){
    if (visited[i][j]) 
        return dp[i][j];
    if (i == j) 
        return 0;
    ll ans = LONG_LONG_MAX;
    for (int k = i; k < j; k++) {
        ll newCost = solve(i, k) + solve(k+1, j) + range_sum(i-1, j);
        ans = min(ans, newCost);
    }
    visited[i][j] = true;
    dp[i][j] = ans;
    return ans;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    prefix[0] = a[0];
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i-1] + a[i];
    }
    memset(visited, false, sizeof(visited));

    cout << solve(0, n-1);
}

Mini Conclusion

The case of the slimes problem, the way the problem transitions subtly described the shape of the graph.

If we tried approaching this simply fromm the perspective of states, it’s not clear at all what representation of state we are suppose to use. However, once we looked not at the vertices but the edges, the shape of our graph becomes self-evident.

Conclusion

Hopefully this blog provided some insight into the intuition behind Dynamic Programming. There are many things I am not able to cover in this short blog. There are some things that simply require experience just never forget what DP is: directed acyclic graph traversal.

One last neat thing about DP is that it’s time complexity is always just the size of the state space.

Things for the eager reader to look up

  1. Backtracking trick (Easy)
  2. Bit set as a state (Intermediate)
  3. DP on a Tree (Intermediate)
  4. DP with Segment Trees (Intermediate)
  5. Convex Hull Trick (Hard)
  6. Divide and Conquer + DP (Hard)
  7. Li Chao Tree and Convex Arrays (Hard)
  8. SMAWK on DP (Hard)
  9. Trick From Aliens / Lagrange Multipliers (Hard)