Why?

Dynamic Programming (DP) is one of the most powerful tools you’ll come across in competitive programming. It normally turns up in about a third of all problems in a contest, in some form or another.

What is it?

Dynamic Programming is a general tactic centred around storing previous calculations so that you don’t need to recompute the outcome of certain functions. While this might seem like common sense, these precomputed calculations can hide themselves quite well.

Example

One of the most popular applications of DP in contests is in solving recurrence relations in a short amount of time. Consider the following problem, Cut Ribbon:

Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions:

• After the cutting each ribbon piece should have length a, b or c.
• After the cutting the number of ribbon pieces should be maximum.

Help Polycarpus and find the number of ribbon pieces after the required cutting.

Input

The first line contains four space-separated integers n, a, b and c (1 ≤ n, a, b, c ≤ 4000) — the length of the original ribbon and the acceptable lengths of the ribbon pieces after the cutting, correspondingly. The numbers a, b and c can coincide.

Output

Print a single number — the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists.

Solution

Let’s try to create a function max_cuts(x), which tells us the maximum number of cuts for a ribbon of size x. We want to compute max_cuts(n).

Since every possible cutting of the ribbon must start with a cut of size a, b, or c, max_cuts(x) must be either max_cuts(x-a)+1, max_cuts(x-b)+1 or max_cuts(x-c)+1 (Assuming base case max_cuts(0) == 0).

Therefore, we can define max_cuts recursively in the following way:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def max_cuts(x):
    if x == 0:
        return 0
    best = 0
    for cut in (a, b, c):
        if x - cut >= 0:
            best = max(best, max_cuts(x-cut) + 1)
    if best == 0:
        # Not possible to cut this length.
        best = -100000
    return best

# We then just call
max_cuts(n)

1
2
3
4
5
6
7
8
9
10

int max_cuts(int x) {
    if (x == 0) return 0;
    int best = 0;
    if (x - a >= 0) best = max(best, max_cuts(x - a) + 1);
    if (x - b >= 0) best = max(best, max_cuts(x - b) + 1);
    if (x - c >= 0) best = max(best, max_cuts(x - c) + 1);
    // Not possible to cut this length.
    if (best == 0) best = -100000;
    return best;
}

However, if you submit this as is, you will almost certainly get TLE, despite n <= 4000. Why is this?

Lets inspect the call tree for max_cuts with n=5, and a, b, c = 1, 2, 3:

As you can see, despite only taking 6 different values, max_cuts is being called a bunch of times, which is unnecessary! Instead, we can save each value with DP!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# DP[x] = max_cut(x) if computed, or -1.n
DP = [-1] * (n+1)n

def max_cuts(x):
    if DP[x] != -1:n
        # If already computed, just return the value!n
        return DP[x]n
    if x == 0:
        DP[x] = 0m
        return DP[x]m
    best = 0
    for cut in (a, b, c):
        if x - cut >= 0:
            best = max(best, max_cuts(x-cut) + 1)
    if best == 0:
        # Not possible
        DP[x] = -100000m
        return DP[x]m
    # Set the DP value, so that future calls to max_cuts(x) just use DP[x].n
    DP[x] = bestn
    return DP[x]m

max_cuts(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

// DP[x] = max_cut(x) if computed, or -1.n
int DP[4002];n

int max_cuts(int x) {
    // If already computed, just return the value!n
    if (DP[x] != -1) return DP[x];n
    if (x == 0) {
        DP[x] = 0;m
        return DP[x];m
    }
    int best = 0;
    if (x - a >= 0) best = max(best, max_cuts(x-a) + 1);
    if (x - b >= 0) best = max(best, max_cuts(x-b) + 1);
    if (x - c >= 0) best = max(best, max_cuts(x-c) + 1);
    if (best == 0) {
        // Not possible.
        DP[x] = -100000;m
        return DP[x];m
    }
    // Set the DP value, so that future calls to max_cuts(x) just use DP[x].n
    DP[x] = best;n
    return DP[x];m
}

int main() {
    // Initiliase DP
    for (int i=0; i<4002; i++) DP[i] = -1;
    cout << max_cuts(n) << endl;
}

This won’t TLE, because we only need to compute 4001 values, max_cuts(x) for any x from 0 to n.