No, I don't mean Convex Hull Trick and Knuth optimization. I mean simpler and more common methods.

This is a continuation of my series of posts on DP, to understand the terminology read the prologue.

Transitions from a segment

Very often after building the DP graph one can discover that the transitions into a state go not from a random set of vertices, but from some segment of values for one of the parameters. For example, from states dp[i][j] with some constant i and j lying in a segment [a, b].

In such cases one may not implement each transition separately, but to implement them all at once. If by implementing a transition we mean adding from dp[A] to dp[B], then we can use prefix sums. In case if we need to find the best transition into dp[B], then we can use Segment Tree.

An Example

AtCoder DP Contest: Problem M Find the number of integer sequences of length n where i-th number is from 0 to a[i] and the sum of numbers is equal to k.

Let's solve it with the Process Simulation approach. Consider a process of writing this sequence number by number. The parameters of the process will be:

1. How many number are already written.

2. The sum of the written numbers.

The value of dp[i][j] will be the number of paths of the process leading into this state.

The amount of transitions of a single state is O(k), the overall amount of transitions is O(n k^2), too much.

Let's consider where the states intodp[i][j] are leading from. Obviously, from dp[i - 1][l] where l belongs to the segment [max(0, j - a[i - 1]), j].

Thus, before counting the layer i, we can count prefix sums on the layer i - 1 in order to count dp[i][j] in O(1).

#include <bits/stdc++.h>

#define int int64_t

using namespace std;

int mod = 1e9 + 7;

int32_t main() {
    ios_base::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> dp(k + 1); // current layer (alleged parameter)
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        vector<int> sum(dp.size() + 1); // prefix sum of the current layer
        for (int j = 0; j < dp.size(); j++) {
            sum[j + 1] = sum[j] + dp[j];
        }
        vector<int> new_dp(k + 1); // next layer
        for (int j = 0; j <= k; j++) {
            new_dp[j] = (sum[j + 1] - sum[max(int64_t(0), j - a[i])]) % mod;
        }
        dp = new_dp;
    }
    cout << dp[k] << endl;
}

Transitions from a sloping segment

Let's return to a problem from a previous part of my blog.

543A - Writing Code There are n programmers that need to write m lines of code and make no more than b mistakes. i-th programmer makes a[i] mistakes per line. How many ways are there to do it? (Two ways are different if the number of lines that some programmer writes differs).

Let's remember our very first solution: define a process where at each step we assign another programmer the number of lines written by him. The parameters will be:

1. The amount of programmers passed by.

2. The total amount of written lines.

3. The total amount of made mistakes.

The value of dp[i][j][k] will be the number of paths of the process leading into this state.

Then there will be O(n m b) states overall and there are O(m) transitions from a single state, so there are O(n m^2 b) transitions overall, which is too much.

But let's consider from which states there is a transition into the state dp[i][j][k]. If the last step was "i - 1-th programmer has written x lines of code" then the transition was from a state dp[i - 1][j - x][k - x * a[i - 1]] (where x >= 0).

So the states from which there is a transitions are located on a line in the table of the i - 1-th layer, and generally such sum can be calculated in O(1) time from an analogous sum for the state dp[i][j - 1][k - a[i - 1]].

After some simplifications, the code will look as follows:

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

int mod;

void add(int& a, int b) { // instead of (a += b) %= mod
    a += b;
    if (a >= mod) {
        a -= mod;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    int n, m, b;
    cin >> n >> m >> b >> mod;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<vector<int>> dp(m + 1, vector<int>(b + 1)); // current layer
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) { // transition from layer i to i + 1
        for (int j = 0; j < m; j++) {
            for (int k = 0; k <= b - a[i]; k++) {
                add(dp[j + 1][k + a[i]], dp[j][k]);
            }
        }
    }
    int ans = 0;
    for (int k = 0; k <= b; k++) {
        add(ans, dp[m][k]);
    }
    cout << ans << endl;
}

Swap the value and a parameter

It's the oldest trick in the book. If one of the parameters is too large and the value is on the contrary limited, one can try swapping their roles.

An Example

AtCoder DP Contest: Problem E There are n objects, i-th one has a weight of w[i] and a value of v[i]. What is the maximal sum of values among all sets of objects, where the sum of weights is no more than m? In this version of the problem n <= 100, m <= 10^9, v[i] <= 10^3.

Let's take the solution from a previous part of the blog: consider a process where on each step a new object is considered and is either picked or skipped, the parameters of the process will be:

1. The number of considered objects.

2. The total weight of the picked objects.

The value of DP will be the largest sum of values of the picked objects for the given state of the process.

With the given constraints the maximal value of the second parameter will be 10^9 and the maximal value of DP will be 10^5, so it makes sense to swap their roles. The process will be the same, but the parameters will be:

1. The number of considered objects.

2. The total value of the picked objects.

The value of DP will be the smallest sum of all weights of the picked objects for the given state of the process.

In the end we will find the largest sum of objects' values among those for which the minimal total weight is no more than W.

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

void relax(int& a, int b) {
    a = min(a, b);
}

const int max_v = 1e5;

int32_t main() {
    ios_base::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<int> w(n), v(n);
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
    }
    vector<int> dp(max_v + 1, 2e18); // if there are no paths leading to that state, the minimal sum is considered to be inf
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        vector<int> new_dp = dp; // automatically implement all the transitions of the first type
        for (int j = 0; j <= max_v - v[i]; j++) {
            // fix the state dp(i)[j], where i is alleged
            relax(new_dp[j + v[i]], dp[j] + w[i]); // transition of the second type
        }
        dp = new_dp; // shift from layer i to i + 1
    }
    int ans = 0;
    for (int i = 0; i <= max_v; i++) {
        if (dp[i] <= m) {
            ans = i;
        }
    }
    cout << ans << endl;
}

Unite two parameters

Sometimes we can notice about two parameters that we don't have to know the value of each separately, instead it's enough to track the value of some combination of them. For example, in case if at the end we do some check on whether the sum of two parameters exceeds some value then it is possible that we can change these two parameters with a one equal to their sum.

An Example

19B - Checkout Assistant There are n products, each has a price of c[i] and the time of processing t[i]. Find a set of products with the smallest total price such that their total time of processing is no less than the number of the remaining products.

Consider a process where on each step a new product is considered and is either picked or skipped. The parameters will be:

1. The number of considered products.

2. Total processing time of the picked products.

3. The number of skipped products.

The value of DP will be the minimal total price of the picked products for a given state of the process.

At the end we are interested in the states dp[n][j][k] where j >= k. As k <= n, after the parameter j has reached n there is no need to increase it any further, so we will write down all the states of the process with the larger values of the parameter j as if j = n.

Thus, the number of states is equal to O(n^3), as is the number of transitions, which does not satisfy the time limit.

Let's have a closer look on where the transitions from the state dp[i][j][k] are leading to: in case if we pick the product – into dp[i + 1][j + t[i]][k], and in case if we skip – into dp[i + 1][j][k + 1].

Notice that in the first case the difference of the second and the third parameters simply increases by t[i], in the second case – decreases by 1, and in the end we need to cut the states in which this difference is non-negative, therefore instead of these two parameters separately, we can instead track their difference.

For convinience instead of j - k we will track j + i - k (so the parameter is never negative, as k <= i), then in case of picking the product the parameter is increased by t[i] + 1, and in case of skipping it doesn't change.

At the end we cut the states where this parameter is no less than n, at the same time it doesn't decrease after any transition, so analogically to the previous solution, we can write down the states with j + i - k > n into dp[i][n].

Thus, the amounts of states and transitions both equal O(n^2).

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

void relax(int& a, int b) {
    a = min(a, b);
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> t(n), c(n);
    for (int i = 0; i < n; i++) {
        cin >> t[i] >> c[i];
    }
    vector<int> dp(n + 1, 2e18); // current layer (alleged parameter)
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        vector<int> new_dp = dp; // implement the transitions of the second type
        for (int j = 0; j <= n; j++) {
            relax(new_dp[min(n, j + t[i] + 1)], dp[j] + c[i]);
        }
        dp = new_dp; // shift to next layer
    }
    cout << dp[n];
}

Conclusion

If you want to know more, I remind that I do private lessons on competitive programming, the price is $30/h. Contact me on Telegram, Discord: rembocoder#3782, or in CF private messages.