Dynamic Programming Problems (Codeforces)

Problem Name Link Rating DP Concept Brief Description

Given two equal-length integers l and r,

find an integer x in [l,r] that minimizes f(l,x)
Sponsor of Your CF *1500
Digit DP +f(x,r), where f counts matching digits.
Problems 1 2121E 2
Solve by trying possible x via digit-DP
(tracking matching prefixes) 1 .

Given n cars on lanes with positions and

speeds, compute minimum time for
Lanes of Cars CF *2300 reaching a destination. Use DP over cars
DP on arrays
3 2120E 4 ordering (e.g. grouping cars) to decide
overtakes or waits to minimize total time.
[See CF problem statement】.

Count assignments under “AND”

constraints: given sequences of
operations, count ways to select
And Constraint CF *2600
Bitmask DP assignments of array to satisfy constraints.
5 2119E 6
Solve by DP over subsets/bitmasks (e.g.,
iterate subsets of bits compatible with
constraints).

Remove tokens on a line in optimal way:

given an array of tokens, maximize score
Token CF *2100
1D DP by choosing removal order. Use DP on
Removing 7 2119D 8
segments: dp[l][r] = best score removing all
tokens from l…r.

Given n operations that add or multiply a

running total, maximize final value. Use DP
Build an Array CF *2200 by processing operations in order,
Greedy+DP
9 2114G 9 employing greedy pruning or knapsack-
like DP on operation counts to maximize
the result.

On each move, increment or decrement

Small CF *2000 digits of a number by given ops to reach
DP on states
Operations 10 2114F 11 target. Solve with DP on digits or states,
tracking remaining operations.

1
Problem Name Link Rating DP Concept Brief Description

Given counts of 0/1 bits and operations

flipping bits, count ways to achieve target
Binary String CF *2400 DP +
bitstrings. Use DP to count valid sequences
Wowee 12 2109E 12 combinatorics
of flips (modulo), often with combinatorial
DP on prefix states.

Escape through grid of rooms with costs:

compute shortest time to escape. Use DP/
Neo’s Escape CF *1500
Graph DP BFS on graph grid states. (Solve by Dijkstra
13 2108C 14
or DP on states representing position and
collected keys.)

Given positions on cycle and cost to build

roads, maximize length of cycle segments
Cycling (Hard) CF *2800 under budget. Use a greedy + DP
Greedy + DP
15 2107F2 16 approach: binary-search answer and check
feasibility via knapsack-like DP on
segments.

Same scenario as hard version but easier

Cycling (Easy) CF *2300
Greedy constraints. Use greedy selection of the
15 2107F1 17
largest segments until budget runs out.

Classic max subarray: find subarray with

Maximum
CF *1500 maximum sum. Solve with Kadane’s
Subarray Sum DP (Kadane’s)
2107C 18 algorithm (O(n) DP): dp[i] = max ending at
18
i.

Goblin collects treasure in directed graph

CF *1900 with time constraint; maximize loot. Use
Goblin 19 DP + Graph
2106F 19 DP over graph in topological order: dp[v] =
max over edges u→v (dp[u] + gain).

Build bouquets with given flowers: choose

CF *1500 from multiple flower types to meet
Flower Boy 20 DP
2106D 20 bouquet criteria. Use knapsack-like DP:
dp[i] = best value using i flowers.

Transform an integer to match a target by

operations on digits. Use DP over digits
Numbers and CF *2600
DP + Math with bitmask: for each subset of digit-
Strings 21 2104F 21
positions, check reachability (FFT or
greedy).

Count palindromic substrings after allowed

Unpleasant CF *1700 letter changes. Use DP on string positions
DP on string
Strings 22 2104E 23 tracking palindromic conditions (expand-
around-center approach).

2
Problem Name Link Rating DP Concept Brief Description

Given devices needing batteries and

Fewer Batteries CF *1700 battery packs with capacities, maximize
DP, knapsack
24 2110D 25 powered devices. Solve with knapsack DP
over capacities (dp[c] = max devices).

Count valid assignments on tree nodes:

Gellyfish and
CF *2100 given tree and choices, count ways mod
Camellia Tree DP
2115B 26 prime. Use DP on tree: dp[v][state]
Japonica 26
combining children’s dp.

Given a target string, count ways to build it

Wonderful City CF *1700 from pieces (substring operations). Use DP
DP
27 2096C 27 over prefixes: dp[i] = number of ways to
form prefix of length i.

Compute max profit of trips on a waterway

Gleb and CF *2300 graph: DP state includes current node and
Graph DP
Boating 28 2091G 29 remaining resource. Use DP on graph
nodes and remaining stops.

Count increasing subsequences with

Igor and CF *1800 constraints: find subsequences in array
DP
Mountain 30 2091F 30 that sum to given value. Use DP: dp[sum]
updating for each element.

Given games with probabilistic outcomes,

compute expected maximum. Use DP over
Key of Like CF *2200 DP +
states (rounds, wins) combined with
(Easy) 31 2089C1 31 Probability
probabilities to compute optimal expected
value.

Assign workers to tasks minimizing cost

Canteen (Hard) CF *2300 under demands. Model as min-cost max-
Min-Cost Flow
32 2089B2 32 flow / DP on subsets: use flow to match
workers to tasks (DP with flows).

Count/construct “zebra” sequences (binary

Zebra-like CF *2400 strings with no two adjacent 1s) under
Bitmask DP
Numbers 33 2086E 33 constraints. Use bitmask DP to enumerate
valid patterns and count.

Remove characters to make a string

“even” (each character appears even
CF *1700
Even String 34 DP on strings times). Use DP on prefix + bitmask of
2086D 34
parity: dp[i][mask] = best removals up to i
with mask.

3
Problem Name Link Rating DP Concept Brief Description

Given strip lengths, maximize folded result:

Another Folding CF *2700 cut strips so lengths form longest
DP + Greedy
Strip 35 2077E 36 sequence under constraints. Use greedy
selection + DP on lengths.

Binary Given binary string, compute sum of

CF *2300
Subsequence DP + FFT values of all subsequences modulo. Use
2077C 37
Value Sum 37 DP/FFT: convolve contributions of each bit.

Fill a matrix of bits to maximize XOR sums.

CF *2500
XOR Matrix 38 DP + Bitmask Use DP over bitmasks: dp[i][mask] = best
2075E 38
filling of first i rows with mask pattern.

Given graph of people liking others,

choose a set making everyone “happy”.
CF *2000
Equalization 39 DP + Graph Model as graph DP: select nodes such that
2075D 39
each node has >=1 selected neighbor
(classic DP on graph).

Choose triangles on a plane to maximize

Game With
CF *2100 area sum with constraints. Use DP by
Triangles: Geometric DP
2074G 40 sorting triangles and using LIS-like DP on
Season 2 40
overlapping conditions.

Adjust attack sequences to defeat a boss in

Do You Love CF *1500
DP + Greedy minimal time. DP tracks remaining health
Your Hero… 41 2072E 41
vs turns; greedy picks largest attacks early.

Given probabilities of events, maximize

CF *2600 DP + expected success with limited moves. DP
LeaFall 42
2071E 42 Probability state: (moves used, current state) to
maximize expectation.

Given operations that append digits,

Infinite
CF *2500 maximize formed number subject to
Sequence Bitmask DP
2071D2 43 pattern. Use bitmask DP for operations
(Hard) 43
sequence building largest number.

Infinite
CF *1800 Easy version of above: use greedy picks of
Sequence (Easy) Bitmask DP
2071D1 44 operations, easier DP or sort by effect.
44

Given cheeses with tastes, arrange tasting

Trapmigiano CF *1700 order to maximize pleasing sequence. Use
DP + Greedy
Reggiano 45 2071C 45 DP on prefix choices (with greedy sorting
by taste).

4
Problem Name Link Rating DP Concept Brief Description

Given a tree and jump lengths, count ways

CF *1600 to pick jumps covering nodes. DP on tree:
Tree Jumps 46 Tree DP
2070D 47 dp[v][k] = ways to cover subtree rooted at v
using k jumps.

Rearrange numbers to maximize “beauty”:

Beautiful CF *1500 match pairs to maximize count of equal
DP + Greedy
Sequence 48 2069C 49 neighbors. Use DP on counts or greedy
matching.

Given a trie of Morse code letters, count

CF *1500 ways to interpret a sequence of signals.
Morse Code 50 DP on Trie
2068D 50 Use DP on positions in signal and trie
nodes.

Compute maximum “blossom” value by

CF *2400 placing petals on nodes. Solve by DP on
Blossom 51 DP + Math
2084E 51 polynomial convolution or inclusion-
exclusion on subsets.

Assign numbers to two groups minimizing

Math Division CF *1800 difference. Equivalent to partitioning
Bitmask DP
52 2081A 52 problem: DP over subsets bitmask to check
feasible equal-sum splits.

Given ads of lengths, fill timeline

Scammy Game CF *1800 maximizing ads shown. DP on intervals:
DP + Greedy
Ad 53 2078D 53 dp[t] = max ads by time t, or greedily pick
longest ads first.

Given a set of binary strings, align them by

Bitwise Slides CF *2300 adding slides to minimize Hamming
Bitmask DP
54 2066C 54 distance. Use DP over bitmasks to try
alignment offsets.

Count ways to select numbers such that

CF *1900 bitwise AND is nonzero. Use DP on
White Magic 55 DP + Math
2066B 55 bitmasks: dp[i][mask] = ways considering
first i numbers with AND = mask.

Assign gifts with constraints: count ways to

Bro Thinks He’s CF *2200 DP + permute assignments meeting conditions.
Him 56 2065H 56 Combinatorics DP on subsets with inclusion-exclusion
(bitmask DP).

Sequential summing game: with array

We Be CF *2600 operations, maximize final sum. Use DP
DP
Summing 57 2064F 57 over positions and current sum (mod large
primes) to find optimal sequence.

5
 Problem Name Link Rating DP Concept Brief Description

Given a circle of pancakes, find a

CF *1900 DP + Two contiguous segment with maximum tasty
Eating 58
2064D 58 pointers sum. Use sliding window DP: two-pointer
for best segment.

Given a tree with nodes labeled 0/1, count

Counting Is Not CF *2400
DP + Bitmask independent sets (“fun” subsets). Use DP
Fun (Easy) 59 2063F1 59
on tree with bitmask of parity conditions.

Count ways to partition tree into subtrees

Triangle Tree CF *2300 of size 3 (triangles). DP on tree: dp[v][k] =
Tree DP
60 2063E 60 ways covering subtree of size k mod 3,
combining children states.

Simulate process with intervals: for each

added segment [l,r], maintain a multiset of
CF *2300
Ice Baby 61 Multiset DP left endpoints, removing any that cannot
2121H 61
extend. The DP is implicit in greedy
segment selection 61 .

Choose subsequence of games to

Big Wins! (Easy) CF *2200 maximize points under constraints. Use DP
Greedy+DP
62 2126G1 62 on prefix sums and greedy merging of
segments to compute best achievable win.

Sources: Problem details and ratings are from the Codeforces problem statements 2 3 12 33 53 54
(rating/tag lines) and associated contest editorials. Each description summarizes the DP approach for the
problem.

1 61 Codeforces Round 1032 (Div. 3) Editorial - Codeforces

https://codeforces.com/blog/entry/143822

2 Problem - 2121E - Codeforces

https://codeforces.com/problemset/problem/2121/E

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 30 31 32

33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 62

Problemset - Codeforces
https://codeforces.com/problemset?tags=dp