Dynamic Programming (II)

Dynamic Programming (II)

Fuzen Ng {yfng}
2024-03-16
 Dynamic Programming (II) 2

Why DP?
● DP is a very common technique in OI

● Some tasks may divide subtasks into different levels of DP

● Some subtasks could be done by DP even the full solution is not DP

 Dynamic Programming (II) 3

How to DP?
● Solve subproblems

● Memorize and reuse the results of the subproblems

 Dynamic Programming (II) 4

Table of Contents
● DAG

● Tree DP

● Bitwise DP

● Memory optimization
 Dynamic Programming (II) 5

Related Tasks on HKOJ for today

M1739 How to Run Fast
M1862 Little Patterns, Big Canvas
T094 Medical Laboratories
I1022 Traffic Congestion
M0712 Maximum Sum II
M2136 Guardian
M1830 Lazy Tutor
 Dynamic Programming (II) 6

If you are too strong

Dreaming (IOI 2013)
Alice and Her Lost Cat (Codeforces gym 104053 A)
Walk Through the Forest (UVA 10917)
XOR Counting (Codeforces 1815 D)
 Dynamic Programming (II) 7

Things you should know

● Bases cases
Subproblems that cannot be reduced

● States
IDs of subproblems

● Transition formula
Using results of subproblems to find the answer
 Dynamic Programming (II) 8

DAG
● Directed Acyclic Graph

● Node = State

● Edge = Transition

● Can be used as a tool to visualize DP transitions

 Dynamic Programming (II) 9

DAG
2
1
5
4
3 7

6
 Dynamic Programming (II) 10

DAG States
2
1
5
4
3 7
Transitions
6
 Dynamic Programming (II) 11

DAG
● DAG is usually applied with topological sort to determine the DP order

2
1
5
4
3 7

6
 Dynamic Programming (II) 12

DAG
● DAG is usually applied with topological sort to determine the DP order

1 2 3 4 5 6 7
 Dynamic Programming (II) 13

DAG - Topological Sort

● Obtain an order of nodes so that if there exist a directed edge from node
A to node B ⇒ node A appears before node B in the order
while some nodes are unvisited
choose any unvisited node
DFS from the node
push the node into a stack
recur to visit an unvisited node
pop from the stack when there are no more unvisited nodes
insert the node into the topological order in reverse order
 Dynamic Programming (II) 14

DAG - Topological Sort

B E
stack H
C
A
D F
G

Topological Order
 Dynamic Programming (II) 15

DAG - Topological Sort

B E
stack H
C
C A
D F
G

Topological Order
 Dynamic Programming (II) 16

DAG - Topological Sort

B E
stack H
C
C A
F
D F
G

Topological Order
 Dynamic Programming (II) 17

DAG - Topological Sort

B E
stack H
C
C A
F
D F
H G

Topological Order
 Dynamic Programming (II) 18

DAG - Topological Sort

B E
stack H
C
C A
F
D F
G

Topological Order
H
 Dynamic Programming (II) 19

DAG - Topological Sort

B E
stack H
C
C A
D F
G

Topological Order
F H
 Dynamic Programming (II) 20

DAG - Topological Sort

B E
stack H
C
C A
G
D F
G

Topological Order
F H
 Dynamic Programming (II) 21

DAG - Topological Sort

B E
stack H
C
C A
D F
G

Topological Order
G F H
 Dynamic Programming (II) 22

DAG - Topological Sort

B E
stack H
C
C A
E
D F
G

Topological Order
G F H
 Dynamic Programming (II) 23

DAG - Topological Sort

B E
stack H
C
C A
D F
G

Topological Order
E G F H
 Dynamic Programming (II) 24

DAG - Topological Sort

B E
stack H
C
A
D F
G

Topological Order
C E G F H
 Dynamic Programming (II) 25

DAG - Topological Sort

B E
stack H
C
A A
D F
G

Topological Order
C E G F H
 Dynamic Programming (II) 26

DAG - Topological Sort

B E
stack H
C
A A
D
D F
G

Topological Order
C E G F H
 Dynamic Programming (II) 27

DAG - Topological Sort

B E
stack H
C
A A
D
D F
B G

Topological Order
C E G F H
 Dynamic Programming (II) 28

DAG - Topological Sort

B E
stack H
C
A A
D
D F
G

Topological Order
B C E G F H
 Dynamic Programming (II) 29

DAG - Topological Sort

B E
stack H
C
A A
D F
G

Topological Order
D B C E G F H
 Dynamic Programming (II) 30

DAG - Topological Sort

B E
stack H
C
A
D F
G

Topological Order
A D B C E G F H
 Dynamic Programming (II) 31

DAG - Topological Sort

● Another way
maintain a set S of nodes with no incoming edge
while S is not empty
pop any node u in S
add u to the topological order
for each edge from u to v
delete the edge (one less incoming edge for v)
if v has no incoming edges
insert v to S
 Dynamic Programming (II) 32

in=1
DAG - Topological Sort in=1

B in=1 E
in=0 H in=2
C
S: A
D F
in=1 G in=1

in=2
Topological Order
 Dynamic Programming (II) 33

in=1
DAG - Topological Sort in=1

B in=1 E
in=0 H in=2
C
S: A A
D F
in=1 G in=1

in=2
Topological Order
 Dynamic Programming (II) 34

in=1
DAG - Topological Sort in=1

B in=1 E
in=0 H in=2
C
S: A
D F
in=1 G in=1

in=2
Topological Order
A
 Dynamic Programming (II) 35

in=1
DAG - Topological Sort in=1

B in=1 E
in=0 H in=2
C
S: A
D F
in=0 G in=1

in=2
Topological Order
A
 Dynamic Programming (II) 36

in=1
DAG - Topological Sort in=1

B in=1 E
in=0 H in=2
C
S: D A
D F
in=0 G in=1

in=2
Topological Order
A
 Dynamic Programming (II) 37

in=1
DAG - Topological Sort in=1

B in=1 E
in=0 H in=2
C
S: A
D F
in=0 G in=1

in=2
Topological Order
A D
 Dynamic Programming (II) 38

in=1
DAG - Topological Sort in=0

B in=1 E
in=0 H in=2
C
S: A
D F
in=0 G in=1

in=1
Topological Order
A D
 Dynamic Programming (II) 39

in=1
DAG - Topological Sort in=0

B in=1 E
in=0 H in=2
C
S: B A
D F
in=0 G in=1

in=1
Topological Order
A D
 Dynamic Programming (II) 40

in=1
DAG - Topological Sort in=0

B in=1 E
in=0 H in=2
C
S: A
D F
in=0 G in=1

in=1
Topological Order
A D B
 Dynamic Programming (II) 41

in=1
DAG - Topological Sort in=0

B in=0 E
in=0 H in=2
C
S: A
D F
in=0 G in=1

in=1
Topological Order
A D B
 Dynamic Programming (II) 42

in=1
DAG - Topological Sort in=0

B in=0 E
in=0 H in=2
C
S: C A
D F
in=0 G in=1

in=1
Topological Order
A D B
 Dynamic Programming (II) 43

in=1
DAG - Topological Sort in=0

B in=0 E
in=0 H in=2
C
S: A
D F
in=0 G in=1

in=1
Topological Order
A D B C
 Dynamic Programming (II) 44

in=0
DAG - Topological Sort in=0

B in=0 E
in=0 H in=2
C
S: A
D F
in=0 G in=0

in=0
Topological Order
A D B C
 Dynamic Programming (II) 45

in=0
DAG - Topological Sort in=0

B in=0 E
in=0 H in=2
C
S: E, F, G A
D F
in=0 G in=0

in=0
Topological Order
A D B C
 Dynamic Programming (II) 46

in=0
DAG - Topological Sort in=0

B in=0 E
in=0 H in=2
C
S: F, G A
D F
in=0 G in=0

in=0
Topological Order
A D B C E
 Dynamic Programming (II) 47

in=0
DAG - Topological Sort in=0

B in=0 E
in=0 H in=1
C
S: F, G A
D F
in=0 G in=0

in=0
Topological Order
A D B C E
 Dynamic Programming (II) 48

in=0
DAG - Topological Sort in=0

B in=0 E
in=0 H in=1
C
S: F, G A
D F
in=0 G in=0

in=0
Topological Order
A D B C E
 Dynamic Programming (II) 49

in=0
DAG - Topological Sort in=0

B in=0 E
in=0 H in=1
C
S: G A
D F
in=0 G in=0

in=0
Topological Order
A D B C E F
 Dynamic Programming (II) 50

in=0
DAG - Topological Sort in=0

B in=0 E
in=0 H in=0
C
S: G A
D F
in=0 G in=0

in=0
Topological Order
A D B C E F
 Dynamic Programming (II) 51

in=0
DAG - Topological Sort in=0

B in=0 E
in=0 H in=0
C
S: G, H A
D F
in=0 G in=0

in=0
Topological Order
A D B C E F
 Dynamic Programming (II) 52

in=0
DAG - Topological Sort in=0

B in=0 E
in=0 H in=0
C
S: H A
D F
in=0 G in=0

in=0
Topological Order
A D B C E F G
 Dynamic Programming (II) 53

in=0
DAG - Topological Sort in=0

B in=0 E
in=0 H in=0
C
S: H A
D F
in=0 G in=0

in=0
Topological Order
A D B C E F G
 Dynamic Programming (II) 54

in=0
DAG - Topological Sort in=0

B in=0 E
in=0 H in=0
C
S: A
D F
in=0 G in=0

in=0
Topological Order
A D B C E F G H
 Dynamic Programming (II) 55

in=0
DAG - Topological Sort in=0

B in=0 E
in=0 H in=0
C
S: A
D F
in=0 G in=0

in=0
Topological Order
A D B C E F G H
 Dynamic Programming (II) 56

DAG - Topological Sort

● S can be implemented by a queue, a stack, anything you like

● Time complexity: O(V + E)

 Dynamic Programming (II) 57

DAG - Number of paths

● How can we use dp to count number of paths of a DAG?

Eg: count number of paths from A to F

1. A → C → E → F A C E
2. A → D → G → E → F
3. A → D → G → C → E → F

● There are three paths in total D G F

 Dynamic Programming (II) 58

DAG - Counting number of paths

● Let paths(x) denote the number of paths from node A to node x

● Since the graph is acyclic, it can be counted as follows:

paths(x) = paths(a1) + paths(a2) + … + paths(ak)

A C E
Where ai are the nodes from which there is
an edge to x
D G F
 Dynamic Programming (II) 59

DAG - Counting number of paths

dp = 1 dp = 2 dp = 3

A C E

D G F
dp = 1 dp = 1 dp = 3
 Dynamic Programming (II) 60

DAG - Practice problem

● M1739 How to Run Fast
● Related to shortest path
● Learned last week!

● M1862 Little Patterns, Big Canvas

● You may refer to slides last 2 years
 Dynamic Programming (II) 61

DAG - M1739 How to Run Fast

● Number of shortest paths from a source in an undirected graph

● Perform Dijkstra to find shortest distance from source to each node

(or any shortest path algorithm you like)

● If (dist[A] + edge_cost == dist[B]) then we add a directed edge from A to B

● Transformed into counting number of paths in DAG

 Dynamic Programming (II) 62

break;
 Dynamic Programming (II) 63

Tree - For those who feel bored

Tree (Codeforces gym 104077 L)
Group Homework (Codeforces gym 104008 G)
The Fox and the Complete Tree Traversal (Codeforces 1819 C)
 Dynamic Programming (II) 64

Tree
2
● A special case of DAG 1 5
(if it is rooted)

● N nodes and N-1 edges 7

3 4
● Exist an unique path from a node
to any other nodes

6 8
Tree rooted
at node 1
 Dynamic Programming (II) 65

Tree - Things you should know

2
● Root, Leaf 1 5
● Parent, Child
7
● Ancestor, Descendant 3 4
● Height, Depth

6 8
● Subtree
 Dynamic Programming (II) 66

Tree DP
● Given a rooted tree - easier

● Given an unrooted tree with bidirectional edges

● You may need to root it yourself
● e.g. by assigning a random node as the root
 Dynamic Programming (II) 67

Tree DP
● Assume a tree is rooted

● Use nodes as DP states

● Use nodes’ children as transition formula reference

 Dynamic Programming (II) 68

Tree DP - Example 0 - Subtree size

● Given a rooted tree of size N
● Calculate the size of each subtree

● For each node, recursively count number of nodes in the subtree

● Time complexity = O(N2)

 Dynamic Programming (II) 69

Tree DP - Example 0 - Subtree size

● Given a rooted tree of size N
● Calculate the size of each subtree

● dp[i] = size of subtree i

● dp[i] = 1 + sum(dp[j]) where j is i’s children

● Each node is visited once only

● Time complexity = O(N)
 Dynamic Programming (II) 70

Tree DP - Example 1 - Subtree max

● Given a rooted tree of size N
● Each node is labeled by a value
Node i has the value v[i]
● Q queries
Find the greatest value in a subtree
 Dynamic Programming (II) 71

Tree DP - Example 1 - Subtree max

● Given a rooted tree of size N
● Each node is labeled by a value
Node i has the value v[i]
● Q queries
Find the greatest value in a subtree

● dp[i] = answer for subtree i

● dp[i] = max(v[i], dp[j]) where j is i’s children

● Each node is visited once only

● Time complexity = O(N)
 Dynamic Programming (II) 72

Tree DP - Example 2 - Painter

● Given a rooted binary tree with size N
● You have to paint all nodes by assigning painter to nodes
● A painter at a node can paint the node itself,
its parent and its immediate children 1
● Find the minimum number of painters required
2 3
Time complexity required : O(N)
4 5

6
 Dynamic Programming (II) 73

Tree DP - Example 2 - Painter

● For each node define 3 dp states:
dp[i][0] = {assign a painter to this node}

dp[i][1] = {this node is covered by its

children node’s painter}
1

dp[i][2] = {this node is not covered by

2 3
any other node}
Take min value in the transition 4 5
Time complexity = O(N)
6
 Dynamic Programming (II) 74

Tree DP - Example 2 - Painter

● Base case(leaf): dp[i][0] = 1, dp[i][1] = 1, dp[i][2] = 0
● Observation: dp[i][2] <= dp[i][1] <= dp[i][0]
○ Not necessary

● consider node i with children j and k:

● dp[i][0] = {assign a painter to node i}
○ 1 + dp[j][2] + dp[k][2]
● dp[i][1] = {node i is covered by its children node’s painter}
○ min(dp[j][0] + dp[k][1], dp[j][1] + dp[k][0])
● dp[i][2] = {node i is not covered by any other node}
○ dp[j][1] + dp[k][1]
 Dynamic Programming (II) 75

Tree DP - Example 3 - Paths passing through

● Given a rooted tree of size N
● Calculate number of simple paths passing through each node
 Dynamic Programming (II) 76

Tree DP - Example 3 - Paths passing through

● Calculate number of simple paths passing through each node

● sz[i] = size of subtree i (Example 0)

● Answer for node x can be calculated with sz[j] where j is x’s children
● Treat x as the root
○ (N - sz[x]) as one of the subtrees
● For each subtree of x,
ans += sz[this subtree] * sum(sz[all other subtrees])
Final answer equals to ans / 2
● Time complexity = O(N)
 Dynamic Programming (II) 77

Tree DP - Practice problem

● T094 Medical Laboratories
● Need to backtrack…

● I1022 Traffic Congestion

● You may refer to slides last 2 years
 Dynamic Programming (II) 78

Tree DP - T094 Medical Laboratories

● dp[i][j] = cost of selecting j leaves in subtree of node i
● if x is a leaf:
○ dp[x][0] = dp[x][1] = 0
● if x has 1 child c:
○ dp[x][j] = dp[c][j]
● if x has 2 children lc and rc:
○ dp[x][i + j] = min(dp[lc][i] + dp[rc][j] + i * j * w[x])

● Record how to reach the minimum answer for backtracking

 Dynamic Programming (II) 79

Tree DP - Summary
● Rooted tree
● DFS from root
● Recursively calculate answers of the children
● Calculate answer for this node
● May require traveling several times to precompute different values
● Subtree size / sum of subtree / height / …
 Dynamic Programming (II) 80

break;
 Dynamic Programming (II) 81

Bitwise DP
● Using bitmask as some states of the dp

● E.g. dp[3][011010012] (dp[3][105])

● Bitmask: a sequence of bits, usually an integer written in binary notation

● Each bit can take on the value of 0 or 1, usually used to represented state
of on / off or being chosen / not being chosen
 Dynamic Programming (II) 82

Bitwise DP - State
● Example 1 (assume the followings are light bulbs):

0 1 2 3 4 5 6 7

● Treating the lit bulbs as 1, unlit bulbs as 0, this state can be represented
by bitmask 011010012 = 20 + 23 + 25 + 26

● We corresponds the i-th bit (counting from right to left) with the i-th light
bulb. In this order, the bitmask can be calculated by Σ2i for i-th bulb being
lit
 Dynamic Programming (II) 83

Bitwise DP - State
● Example 2 (0-1 Knapsack Problem):
● Given N items with weight wi and value vi, you may pick a subset of items
such that their total weight ≤ K. Find the maximum total value of items
picked
● As with the previous example, each subset can be represented by a
bitmask (i-th item ↔ i-th bit), and can be fitted into a dp state

● Although there exist better solution, coming up with state of bitmask dp is

usually easy and can earn you some basic marks
 Dynamic Programming (II) 84

Bitwise DP - Bitwise Tricks

● Bit manipulation tricks are useful in bitwise dp

● Bitwise AND (&)

● Bitwise OR (|)
● Bitwise XOR (^)
● Bitwise SHIFT (<<, >>)
○ x << y: Shift x left by y bits
○ 5 << 4 = 80 (510 = 1012, 8010 = 10100002)
 Dynamic Programming (II) 85

Bitwise DP - Bitwise Tricks

● Test j-th bit on i
if (i & (1 << j))
● Get i ones from the least significant bit
(1 << i) - 1
● Is i a submask of j?
(i & j) == i
● Enumerate non-empty submasks of j (from large to small)
for (int i = j; i > 0; i = (i - 1) & j)
 Dynamic Programming (II) 86

Bitwise DP - Transition
● Given N light bulbs (N ≤ 15), M buttons, each toggles (on → off, off → on)
a set of light bulbs (Bi - in bitmask form) when pressed (M ≤ 30)
● Find minimum number of times of pressing the buttons to achieve a given
state (K) Or output ”impossible”
 Dynamic Programming (II) 87

Bitwise DP - Transition
● Given N light bulbs (N ≤ 15), M buttons, each toggles (on → off, off → on)
a set of light bulbs (Bi - in bitmask form) when pressed (M ≤ 30)
● Find minimum number of times of pressing the buttons to achieve a given
state (K) Or output ”impossible”

● dp[i][bitmask]: Considering only button 1 to i, the minimum number

of presses needed to achieve the light bulb state in bitmask
● Base case: dp[0][0] = 0
● Answer: dp[M][K]
● Transition: dp[i][bitmask] = min(____)
 Dynamic Programming (II) 88

Bitwise DP - Transition
● For each button, either choose to press it, or not press it
● dp[i][bitmask]: Considering only button 1 to i, the minimum number
of presses needed to achieve the light bulb state in bitmask

● Transition (assume unachievable states are handled):

dp[i][bitmask]
= min(dp[i - 1][bitmask ^ B[i]] + 1, dp[i - 1][bitmask])
● Time complexity: O(M * 2N)
 Dynamic Programming (II) 89

Bitwise DP - M0712 Maximum Sum II

● Given N×N positive integers
● Find the maximum sum of N numbers
● No two numbers are on the same row or the same column

● 1 ≤ N ≤ 16
 Dynamic Programming (II) 90

Bitwise DP - M0712 Maximum Sum II

● dp[i][bitmask] = the maximum sum of i numbers from the first i rows, by
choosing columns represented by the bitmask

● Transition:
for each column j
if (bitmask & (1 << j) == 0)
dp[i][bitmask + (1 << j)] = max(dp[i][bitmask + (1 << j)],
dp[i - 1][bitmask] + a[i][j])

● Answer: dp[N][2N - 1]
● Time complexity: O(N2 * 2N)
 Dynamic Programming (II) 91

Bitwise DP - M0712 Maximum Sum II

● Transition:
for each column j
if (bitmask & (1 << j) == 0)
dp[i][bitmask + (1 << j)] = max(dp[i][bitmask + (1 << j)],
dp[i - 1][bitmask] + a[i][j])

● precompute number of 1s in all bitmasks

○ __builtin_popcount(bitmask)
● For each i, only consider bitmasks that number of 1s equals i - 1
● Time complexity: O(N * 2N)
 Dynamic Programming (II) 92

Bitwise DP - M2136 Guardian

● N witches, each with strength Si and after effect Ei
● Need to fight all witches one by one
● Choosing witch x as the first one to fight against costs SX % M energy
● For 2 ≤ j ≤ N , choosing witch x as the jth one to fight against and witch y
as the j − 1th one to fight against costs ( j × SX × Ey ) % M energy
● Find minimum sum of energy to fight N witches with optimal order
 Dynamic Programming (II) 93

Bitwise DP - M2136 Guardian

The bit (1 << i) in the bitmask represent whether witch i is already chosen

● dp[i][j] = the minimum cost to choose the witches represented by the

bitmask j while the most recently chosen one is witch i

● Base case: dp[i][1 << i] = si % M, other states = inf

● Calculate the dp states with an increasing order of witches chosen, which

is the number of 1s in the bitmasks
 Dynamic Programming (II) 94

Bitwise DP - M2136 Guardian

● For each bitmask j and some i such that (j & (1 << i) != 0)
○ (i is already chosen in j)
● Try all k that (j & (1 << k) == 0)
○ (k is not chosen in j)
● Update dp[k][j ^ (1 << k)] with dp[i][j] + cnt * Sk * Ei % M
○ cnt = (number of 1s in j) + 1

● Answer = minimum of dp[i][(1 << N) - 1]

● Time complexity: O(N2 * 2N)

 Dynamic Programming (II) 95

Bitwise DP - Practice Problem

● M1830 Lazy Tutor
● You may refer to 2018 minicomp 3 editorial
 Dynamic Programming (II) 96

Memory optimization - Rolling Array

● Optimization on memory usage

● Avoid saving data that is no longer useful

● Tiny improvement on runtime

 Dynamic Programming (II) 97

Memory optimization - Rolling Array

● Solve the following problem with DP
● N * M grid
● Calculate the number of ways to move from (1, 1) to (N, M) with right and
down movement only
 Dynamic Programming (II) 98

Memory optimization - Rolling Array

● Solve the following problem with DP
● N * M grid
● Calculate the number of ways to move from (1, 1) to (N, M) with right and
down movement only
● dp[i][j] = number of ways to move from (1,1) to (i, j)
● dp[1][1] = 1
● dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

● Memory complexity = O(NM)

 Dynamic Programming (II) 99

Memory optimization - Rolling Array

● dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
● Only dp[i - 1][1..M] is needed
● dp[i][1..M] can be calculated without referring dp[1..i-2][1..M]

● Keeping two rows of dp states is enough

● Alternatively use dp[0][1..M] and dp[1][1..M] for 1 to N

● Memory complexity = O(M)

● Swapping N and M if M > N ⇒ O(min(N, M))

 Dynamic Programming (II) 100

Memory optimization - Rolling Array

● dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

● In this case, keeping one row of dp states is also enough

● Use dp[1..M] and compute N times
 Dynamic Programming (II) 101

More Practice Problems

M0422 Christmas Tree NP1722 寶藏
T153 Congressman Lee Sin CSES Elevator Rides
CF839C Journey CF1285D Dr. Evil Underscores
CF gym 103470H Crystalfly CF1391D 505
Atcoder abc246G Game on Tree 3 CF1103D Professional layer

I0011 Palindrome
T003 Scheduling Lectures
I0721 Miners
 Dynamic Programming (II) 102

Additional Readings
● SOS Dynamic Programming [Tutorial] - Codeforces
● [Tutorial] Non-trivial DP Tricks and Techniques - Codeforces