Dynamic Programming (DP) is really simple; It’s just STATES and TRANSITIONS. People find DP hard but it’s dead simple to code, easy to analyze, and gives itself away from the shape of the problem space. ¯_(ツ)_/¯

When first learning DP, we usually start with top down or bottom up DP. By the end of this blog, I hope that everyone will start seeing dp in terms of state and transitions.

As a setup, let’s first muse about the nature of top down and bottom up dp.

When we do top down DP, we think recursively. You know recursion! Just have a function call itself with slightly different parameters!

Well, a property of recursion is that the call graph must not have cycles. Proof? Well, your program terminates so there can’t be an cycle.

Second, there is a topological ordering to the function call graph. Why? Well, the call graph is a tree. There’s the first call, then it fans out without ever calling back to an earlier state (doing otherwises would lead to a cycle which we know can’t exist) until reaching the base case.

When we start talking abstractly about “state” and why you can loop through an array with recursion, it’s because we maintain the index of our metaphorical for loop through the parameters of our function calls. The function parameters represents “state”.

In dynamic programming, we break our problem down into russian nesting dolls. Problem solutionns are composed of solutions for its sub-problems. Our state in dynamic programming is the sub-problems to compute.

This top down approach has been argued to be the correct way to think about dp. I agree in principle because we can see the decomposition of problem quite clearly with this recursive framework.

In practice, however, I find bottom up dp to map more intuitively to the shape of many of the classic dp problems.

If you are thinking of DP from a bottom up perspective (like dp[n] = sum(dp[n-1], dp[n-2]), we can see that our indexes are actually just shallow representation of the concept of states. Since we know DP has 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 a_i 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 ≤ a_i ≤ 3

Core 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, 4³⁰⁰. 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” — random icpc 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 a_i 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 ≤ a_i ≤ 10⁹

Core 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, n²)

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. The obsession with looking for the “state” though is useful even outside of DP.

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