Dynamic Programming - CSES Problem Set Solutions

I solved all problems on this page without any hints/spoilers (not even reading the CSES recommended book).

Visit https://cses.fi/problemset/ for the full problem set.

I don't provide the full problem specifications on this page due to possible copyright issues. Links to the original problem specs are provided below along with the date accessed, which should allow you to use Internet Archive if the original URL hosting a problem specification ever meaningfully changes.

Dice Combinations [Spec] (2024-03-13)

The subproblem is simply a Fibonacci-esque recursive function:

With DP, this runs in $O(n)$ time. Considering how the input bounds set $n \le {10}^6$, a test case can in theory run a hotspot $6 \times {10}^6$ times.

We choose $F_{n-1}$ through to $F_{n-6}$ since we know each dice roll has to be integers 1-6.

My first attempt was a top-down implementation, though it comes to no surprise that it causes runtime errors (presumably stack overflow):

Setting a higher setrecursionlimit fixed the runtime errors, but instead TLE’s. Not too surprising. Implementation:

Switching to a simple top-down approach passed all tests (worst-case runtime in CPython and PyPy3 was 1.00s and 0.22s, respectively):

#!/usr/bin/env python3

MOD = int(1e9 + 7)

n = int(input())

tab = [1]
for _ in range(n):
    window_size = min(len(tab), 6)
    tab.append(sum(tab[-window_size:]) % MOD)
print(tab[-1])

Switching to only storing a fixed-size window reduced the worst test case runtimes to 0.44s and 0.13s (CPython and PyPy3, respectively):

#!/usr/bin/env python3

MOD = int(1e9 + 7)

n = int(input())

tab = [0, 0, 0, 0, 0, 1]
for i in range(n):
    tab[i % 6] = sum(tab) % MOD
print(tab[(n - 1) % 6])

Making it so we don’t re-add all six elements of tab anymore turned out to perform worse:

#!/usr/bin/env python3

MOD = int(1e9 + 7)

n = int(input())

tab = [0, 0, 0, 0, 0, 1]
this_sum = 1
for i in range(n):
    i %= 6
    old = tab[i]
    tab[i] = this_sum
    this_sum = ((this_sum * 2) - old) % MOD
print(tab[(n - 1) % 6])

Minimizing Coins [Spec] (2024-03-31)

The first subproblem that comes to mind is, for every integer from $0$ to $x$, we find the fewest number of coins possible. Runtime is $O(xn)$:

Considering how the input bounds set $n \le 100$ and $x \le {10}^6$, a test case can in theory run a hotspot ${10}^8$ times. Assuming a similar style of implementation to my first Dice Combinations passed solution which had a worst runtime of 0.22s, it doesn’t sound like Minimizing Coins in Python should pass since we get a hotspot running at least 10x as many times.

For fun, we start with a Python top-down solution, as well as bottom-up, and I also tried an optimization that precomputes some trivial table entries. The logic appears correct, but they TLE as expected:

Implementing the bottom-up approach in C++ passed all tests (with a longest runtime of 0.15s):

#include <iostream>
#include <vector>
#include <limits>

constexpr long LONG_MAX = std::numeric_limits<long>::max();

int main() {
    long n, targetSum;
    std::cin >> n >> targetSum;

    std::vector<long> coins;
    for (long i = 0; i < n; ++i) {
        long tmp;
        std::cin >> tmp;
        coins.push_back(tmp);
    }

    std::vector<long> tab(targetSum + 1, LONG_MAX - 1);
    tab[0] = 0;

    for (long i = 1; i <= targetSum; ++i) {
        for (const auto coin : coins) {
            if (coin <= i) {
                tab[i] = std::min(tab[i], tab[i - coin]);
            }
        }
        ++tab[i];
    }

    std::cout << ((tab[targetSum] == LONG_MAX) ? -1 : tab[targetSum]) << std::endl;
    return 0;
}

Coin Combinations I [Spec] (2024-04-01)

Different orderings of the same set of coins count as different combinations, which makes subproblem selection easier. My chosen subproblem is to find the number of combinations for each possible target sum $0$ to $x$. For $n$ coins, the runtime is $O(xn)$:

Input bounds are similar to Minimizing Coins, so a hotspot possibly runs ${10}^8$ times, and is similarly unlikely to pass using Python.

But let’s write a top-down Python implementation anyway! As expected, it TLE’s:

Implementing bottom-up in C++ passes all tests:

#include <iostream>
#include <vector>

constexpr long MOD = 1e9 + 7;

int main() {
    long n, targetSum;
    std::cin >> n >> targetSum;

    std::vector<long> coins;
    for (long i = 0; i < n; ++i) {
        long tmp;
        std::cin >> tmp;
        coins.push_back(tmp);
    }

    std::vector<long> tab(targetSum + 1, 0);
    tab[0] = 1;

    for (long i = 1; i <= targetSum; ++i) {
        for (const auto coin : coins) {
            if (coin <= i) tab[i] = (tab[i] + tab[i - coin]) % MOD;
        }
    }

    std::cout << tab[targetSum] << std::endl;
    return 0;
}

Coin Combinations II [Spec] (2024-04-01)

If we used the strategy from Coin Combinations I, we run into the problem of needing to avoid double-counting combinations. To deal with this, maybe we need a two-dimensional table: one dimension for coin value, and another dimension for coin sum. The following subproblem comes to mind, which may naively run in $O(x^2 n)$ time:

I say “naively” because there may be a way to cut that runtime to $O(xn)$ with a clever optimization. I’ll get to my idea for that later.

I am very certain $O(x^2 n)$ will TLE, but I made a top-down Python implementation anyway just for fun. It passes some tests, but TLE’s everything else. Good to know that we’re not getting any wrong answers! Implementation:

Let’s have a look at my $O(xn)$ idea now. I’d use the same subproblem and implement it bottom-up, but I’d fill up the table with the help of an accumulator, which should let me avoid doing the whole $\sum_{j=0}^{\infty}$ summation in $O(x)$ time each time. Instead, the accumulator calculates this summation in $O(1)$ on average.

It’s probably easier to just see how this works in code.

My first implementation works perfectly fine on my computer, but causes weird RUNTIME ERRORs on some test cases when I submit to CSES. I have a screenshot included in the spoiler block below. My code provides the correct answers when I run them on my computer, and none of them TLE, so… I’m not sure what’s going on. Full implementation:

(If anyone knows why I’m getting RUNTIME ERROR, I’d love to know!)

I improved on this solution by changing to a more space-efficient 1D vector, which did pass all test cases:

#include <iostream>
#include <vector>

constexpr long MOD = 1e9 + 7;

int main() {
    long n, targetSum;
    std::cin >> n >> targetSum;

    std::vector<long> coins;
    for (long i = 0; i < n; ++i) {
        long tmp;
        std::cin >> tmp;
        coins.push_back(tmp);
    }

    std::vector<long> tab(targetSum + 1, 0);
    tab[0] = 1;

    for (const auto coin : coins) {
        for (long offset = 0; offset < coin; ++offset) {
            long acc = 0;
            for (long i = offset; i <= targetSum; i += coin) {
                acc = (acc + tab[i]) % MOD;
                tab[i] = acc;
            }
        }
    }

    std::cout << tab[targetSum] << std::endl;
    return 0;
}

TODO: Were the RUNTIME ERRORs to do with the way I implemented the 2D table as 2D vectors?

Removing Digits [Spec] (2024-04-03)

The first subproblem that comes to mind finds the minimum number of steps for each number from $0$ to $n$. It runs in $O(n \log_{10} n)$ since there are $O(n)$ entries in the 1D table, and at each entry, you check every decimal digit (which is $O(\log_{10} n)$). The subproblem written out:

For fun, I started with a Python top-down implementation, which TLE’s as expected, but also didn’t give any wrong answers:

My bottom-up implementation in Python passed all tests:

#!/usr/bin/env python3

n = int(input())

tab = [0]*(n + 1)
for v in range(1, n + 1):
    solution = n  # arbitrary large number
    v2 = v
    while v2 > 0:
        digit = v2 % 10
        if digit:
            solution = min(solution, tab[v - digit])
        v2 //= 10
    tab[v] = 1 + solution

print(tab[-1])

It also passed all tests when I used string conversion to get the digits:

#!/usr/bin/env python3

n = int(input())

tab = [0]*(n + 1)
for v in range(1, n + 1):
    tab[v] = 1 + min(tab[v - int(c)] for c in str(v) if (c != '0'))

print(tab[-1])

Grid Paths [Spec] (2024-04-03)

The fact that paths can only move in one direction makes this problem so much easier since you don’t have to worry about paths backtracking. The first subproblem that comes to mind is to, at each cell in the grid, you add up how many paths can come from above with how many paths can come from the left. It runs in $O(n^2)$ (or more usefully, $O(N)$ for $N$ total cells in the grid):

Surprisingly, a Python top-down implementation using @functools.cache (and running on CPython3) almost passed, but TLE’d on only 2 out of the 15 test cases:

It took 0.99s for one of the passed $1000 \times 1000$ test cases, which indicates to me that not only should Python be feasible, but Python top-down is likely to be feasible as well if I can lower the overhead. And indeed it did pass, although the code isn’t quite that nice since I’m implementing my own memoization:

#!/usr/bin/env python3

from sys import stdin, setrecursionlimit

setrecursionlimit(int(2e6))

MOD = int(1e9 + 7)

n = int(stdin.readline())
grid = [s.strip() for s in stdin.readlines()]

memo = [[None]*n for _ in range(n)]
memo[0][0] = 1

def dp(i, j):
    if (i < 0) or (j < 0) or grid[i][j] == '*':
        return 0
    elif memo[i][j] is None:
        memo[i][j] = (dp(i - 1, j) + dp(i, j - 1)) % MOD
    return memo[i][j]

print(dp(n - 1, n - 1))

My bottom-up implementation is also a bit obscured since I used some tricks to avoid adding if-statements to the main loop (and therefore unnecessary overhead). Here, I pad the grid with an extra row and column (on the top and left sides) so that we automatically get zeroes for paths that try to come from outside of the grid. Implementation:

#!/usr/bin/env python3

from sys import stdin

MOD = int(1e9 + 7)

n = int(stdin.readline())
grid = ["*"*(n + 1), *("*" + s.strip() for s in stdin.readlines())]

tab = [[0]*(n + 1) for _ in range(n + 1)]
tab[0][1] = 1  # intentionally initialized the cell adjacent to the starting cell

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if grid[i][j] == '.':
            tab[i][j] = (tab[i - 1][j] + tab[i][j - 1]) % MOD

print(tab[-1][-1])

Book Shop [Spec] (2024-04-03)

This is the classic 0-1 knapsack problem, which I’ve already done a very detailed writeup on (here), so unfortunately, I’ve already been very thoroughly spoiled on this problem.

The subproblem has two dimensions: “the current book”, and current max cost of currently selected books (from $0$ to $x$). At each “current book” (and corresponding current max cost), we find out what the best possible number of pages is whether or not we purchase the current book. It runs in $O(nx)$:

My first top-down Python implementation TLE’d as I expected:

Implementing bottom-up Python with a full $O(nx)$-sized table caused many RUNTIME ERROR results, but they otherwise gave me correct answers on my computer (albeit very slowly):

My more optimized bottom-up Python implementation that instead uses a $O(x)$-sized table TLE’d, even on PyPy3:

Reimplementing this optimized bottom-up solution in C++ passes all tests with a worst runtime of only 0.15s:

#include <iostream>
#include <vector>

int main() {
    long n, maxSum;
    std::cin >> n >> maxSum;

    std::vector<long> costs {0};  // padded with an extra dummy element so we can 1-index
    for (long i = 0; i < n; ++i) {
        long tmp;
        std::cin >> tmp;
        costs.push_back(tmp);
    }

    std::vector<long> pages {0};  // padded with an extra dummy element so we can 1-index
    for (long i = 0; i < n; ++i) {
        long tmp;
        std::cin >> tmp;
        pages.push_back(tmp);
    }

    std::vector<long> realTab0(maxSum + 1, 0);
    std::vector<long> realTab1(maxSum + 1, 0);
    std::vector<long> *tab0 = &realTab0;
    std::vector<long> *tab1 = &realTab1;
    for (long i = 1; i <= n; ++i) {
        for (long curMaxSum = 1; curMaxSum <= maxSum; ++curMaxSum) {
            if (curMaxSum < costs[i]) {
                (*tab1)[curMaxSum] = (*tab0)[curMaxSum];
            } else {
                (*tab1)[curMaxSum] = std::max(
                    (*tab0)[curMaxSum - costs[i]] + pages[i],
                    (*tab0)[curMaxSum]
                );
            }
        }
        std::swap(tab0, tab1);
    }

    std::cout << (*tab0)[maxSum] << std::endl;
    return 0;
}

Array Description [Spec] (2024-04-03)

The first subproblem that comes to mind has two dimensions: current position in the array description, and candidate value for the position. At each position, we simply count the number of possible “paths” coming from the start of the array. The runtime is $O(nm)$.

What I mean by “path” is, let’s pretend that the beginning of the array (index 0) is known to be the value 5. From index 0, we might be able to “walk” to three different positions in index 1: {index 1, value 4}, {index 1, value 5}, and {index 1, value 6}. We say that there are valid “paths” from the beginning of the array to these three positions. These paths may extend all the way through the array, constrained by the known array values.

TODO: I should illustrate what I mean by a “path”.

The subproblem written out:

A top-down implementation in Python TLE’d, but otherwise gave no wrong answers:

Changing to a bottom-up with a full $O(nm)$ sized table passed all tests with a PyPy3 worst-case runtime of 0.33s:

#!/usr/bin/env python3

from sys import stdin

MOD = int(1e9 + 7)

(_, max_v) = [int(s) for s in stdin.readline().strip().split()]
desc = [int(s) for s in stdin.readline().strip().split()]

tab = [[0]*(max_v + 2) for _ in range(len(desc))]

if desc[0] == 0:
    tab[0] = [0, *(1 for _ in range(max_v)), 0]
else:
    tab[0][desc[0]] = 1

for i, known_v in enumerate(desc[1:], start=1):
    it = range(1, max_v + 1) if (known_v == 0) else (known_v,)
    for v in it:
        tab[i][v] = (tab[i - 1][v] + tab[i - 1][v - 1] + tab[i - 1][v + 1]) % MOD

print(sum(tab[-1]) % MOD)

Improving on the bottom-up solution by switching to an $O(m)$ table also passed, but now with a PyPy3 worst-case runtime of 0.13s:

Counting Towers [Spec] (2024-04-04)

This one’s a hard one! But also a fun one! Let’s start by enumerating some simple examples to get a feel for how this works:

n=1  --> solution=2

AB  AA

n=2  --> solution=8

CD       AB  BA  AB
AB       AC  CA  AB

AA       AA  BC  AA
AA       BC  AA  BB

The first idea that comes to mind is to try a subproblem with two dimensions: the $x$ and $y$ coordinates of the top-right of the tower, where the bottom-left corner is at coordinates $\parens{0, 0}$. Let’s call this subproblem $F\brackets{x, y}$. $x$ is the column index while $y$ is the row index. However, it doesn’t work well:

The next idea that comes to mind is also two dimensions, with one dimension for height of the left side, and one for the right side. It naively sounds like it should perform poorly at $O(n^2)$ where $n \le {10}^6$, but maybe we can apply the same trick as Coin Combinations II where we use an accumulator?

Let’s start by visualizing what’s going on then formalizing the subproblem:

Case 1: Both sides same level
        We arbitrarily pick the top-right block to be fixed.

   F[3,3] = F[3,2] + F[3,1] + F[3,0] + F[2,2] + F[1,1] + F[0,0]

     ??       ?        ?        ?
     ??   =   ??   +   ?    +   ?    +   ??   +        +
     ??       ??       ??       ?        ??       ??

Case 2: Left side is taller
        We pick the tallest block to be fixed.

   F[3,2] = F[2,2] + F[1,2] + F[0,2]

     ?
     ??   =   ??   +    ?   +    ?
     ??       ??       ??        ?

Case 3: Right side is taller
        We just mirror it.

   F[2,3] = F[3,2]

      ?       ?
     ??   =   ??
     ??       ??

Writing out the subproblem:

I made a naive top-down Python implementation and ran it against the example and it passed! However, it was really, really, terribly slow. Implementation:

In an attempt to optimize, I tried expanding some calculations to get a feel for what we might build accumulators for. However, I found nothing. Here’s what I tried:

I also tried expanding out the $F\brackets{x, 0}$’s:

I also tried expanding the $F\brackets{x, x}$’s:

So let’s try a different approach. I believe that the following sums should be easy to build accumulators for:

But this sum is giving me headaches right now:

That sum is an important part of the second line of the subproblem. So is it possible to build an accumulator for it?

Now, let’s visualize what’s happening. For example, $S\brackets{4}$ is the sum of all of these:

Using the third case of the subproblem, we can reduce this to:

Based on this pattern, $S\brackets{b}$ is reducible to:

Therefore, we can calculate $S\brackets{b}$ using accumulators!

Let’s now construct an alternative subproblem derived from this, where $F'\brackets{n}$ is the solution for the number of combinations to construct an $n$-sized tower:

Attempting to simplify seems… too complicated for me to bother right now.

My Python top-down implementation passed the first two test cases containing queries for $n \le 100$, but we get RUNTIME ERROR for the other much bigger test cases, so my code probably goes over the memory usage limit of the auto-judge. Implementation:

Reimplementing as bottom-up passed all tests:

#!/usr/bin/env python3

from sys import stdin

MOD = int(1e9 + 7)

stdin.readline()
tests = [int(s) for s in stdin.readlines()]

tab = [(1, 1, None, None), (2, 3, 1, 1)]  # [(f_val, f_cum, s_val, s_cum), ...]
for _ in range(max(tests) - 1):
    (f_val, f_cum, s_val, s_cum) = tab[-1]
    s_val_new = (f_cum + (2 * s_cum)) % MOD
    f_val_new = (s_val_new + f_cum) % MOD
    tab.append((
        f_val_new,
        (f_val_new + f_cum) % MOD,
        s_val_new,
        (s_val_new + s_cum) % MOD,
    ))

for height in tests:
    print(tab[height][0])

Edit Distance [Spec] (2024-04-08)

Thinking through some edge cases, it was tempting to conclude that you’d never need to remove characters from the shorter word, but I believe this would break that assumption:

Test case:
   xxABCDEFGH
   ABCDEFGHxxx

The actual edit distance is 5:
   xxABCDEFGH   (0)
   xABCDEFGH    (1)
   ABCDEFGH     (2)
   ABCDEFGHx    (3)
   ABCDEFGHxx   (4)
   ABCDEFGHxxx  (5)

If we disallowed removing characters:
   xxABCDEFGH   (0)
   AxABCDEFGH   (1)
   ABABCDEFGH   (2)
   ...
   ABCDEFGHGH   (8)
   ABCDEFGHxH   (9)
   ABCDEFGHxx   (10)
   ABCDEFGHxxx  (11)

The first subproblem that comes to mind is two-dimensional, each dimension is an index into each string. Subproblem $F\brackets{i, j}$ is the edit distance of substrings string1[0..i] and string2[0..j] (i and j being inclusive).

I jumped straight into coding a solution first. Here’s my Python top-down solution that passes many test cases but only fails due to RUNTIME ERROR (almost certainly due to memory usage):

Writing out the subproblem:

The first case is simply the case of two empty substrings. Naturally, empty substrings are already equivalent.

The second and third cases are the case where you compare an empty substring with a non-empty substring. Naturally, the solution is just the length of the non-empty substring.

My top-down Python solution simplifies these first three cases down with essentially:

assert (i >= -1) and (j >= -1)
if (i < 0) or (j < 0):
    return i + j + 2

The fourth case is the case where the two indices point to an equivalent character. This means no change needs to be made at that character.

The final case is where the two indices don’t point to an equivalent character. There’s a lot going on in that one line, so to see how this works, let’s consider this example:

              v i=4
string 1: ...AB...
string 2: ..XY.....
             ^ j=3

The dots represent characters that we don’t care about. Index i points to that B character in string 1, while index j points to that Y character in string 2.

To make it easier to understand, let’s write this situation down in two different but conceptually identical ways:

Recall that the problem specification allows these operations:

1. Add one character to the string.
2. Remove one character from the string.
3. Replace one character in the string.

Let’s start with operation 3 because it’s the simplest. Let’s suppose we change the B in string 1 to Y:

The math works out identically even if we instead changed the Y in string 2 to B:

Now, let’s try operation 2. If we remove B from string 1:

Or if we remove Y from string 2 instead:

And finally, let’s try operation 1. If we insert Y to string 1:

And if we instead insert B into string 2:

Having gone through all six possible operations, it should be fairly straightforward to see how we get $1 + \min\parens{F\brackets{i - 1, j - 1}, F\brackets{i - 1, j}, F\brackets{i, j - 1}}$ as the final case of the subproblem.

I think it’s also useful to point out that the equivalence of $F_{21} = F_{12}$ and $F_{22} = F_{11}$ can also be examined more intuitively.

Let’s consider these two strings:

AXXX
XXX

To make them equivalent, you can either delete the A from string 1:

XXX
XXX

or, you can add an A to string 2:

AXXX
AXXX

Either way, we incurred a cost of $1$ operation.

My Python bottom-up implementation passes all tests:

#!/usr/bin/env python3

(s1, s2) = (input(), input())

tab = [[i]*(len(s2) + 1) for i in range(1, len(s1) + 1)]
# extra row and column, useful for negative indexing
tab.append(list(range(1, len(s2) + 2)))
tab[-1][-1] = 0

for i in range(len(s1)):
    for j in range(len(s2)):
        if s1[i] == s2[j]:
            tab[i][j] = tab[i - 1][j - 1]
        else:
            tab[i][j] = 1 + min(tab[i - 1][j - 1], tab[i - 1][j], tab[i][j - 1])

print(tab[-2][-2])