These notes sketch dynamic programming lectures. Dynamic programming is treated in any introductory book on Algorithms. You may refer to Chapter 15 of Introduction to Algorithms, 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press, 2009 for a more detailed explanation and Chapter 6 of Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani see here.
These are rough and non-exhaustive notes that I used while lecturing. Please use them just to have a list of the topics of each lecture and use other reported references to study these arguments.
Feel free to send a pull request to fix any typo or to clarify any obscure description.
Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to subproblems.
Divide-and-conquer algorithms partition the problem into disjoint subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem.
In contrast, dynamic programming applies when subproblems overlap, that is, when subproblems share subsubproblems.
In this context, a divide-and-conquer algorithm does more work than necessary, repeatedly solving the common subsubproblems.
A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table. Thus, avoiding the work of recomputing the answer every time it solves each subsubproblem.
Fibonacci numbers are defined as follows.
Our goal is to compute the $n$th Fibonacci number
Consider the following trivial recursive algorithm.
uint64_t Fibonacci(uint64_t n) {
if (n == 0) return 0;
if (n == 1) return 1;
else return Fibonacci(n-1) + Fibonacci(n-2);
}The time complexity of this algorithm is given by the recurrence
Thus, for
Memoization is the trick that allows to reduce the time complexity. Whenver we
compute a Fibonacci number, we store it in a array
uint64_t FibonacciMemo(n) {
if (n == 0) return 0;
if (n == 1) return 1;
if (M[n] == NULL) M[n] = FibonacciMemo(n-1) + FibonacciMemo(n-2);
return M[n];
}This algorithm requires linear time and space.
Actually, there is a more direct bottom-up approach which uses linear time and constant space. How?
This approach typically depends on some natural notion of the "size" of a subproblem, such that solving any particular subproblem depends only on solving "smaller" subproblems.
We sort the subproblems by size and solve them in size order, smallest first. When solving a particular subproblem, we have already solved all of the smaller subproblems its solution depends upon, and we have saved their solutions.
We solve each sub-problem only once, and when we first see it, we have already solved all of its prerequisite subproblems.
In our Fibonacci problem this approach correspond to compute an array
We can fill this array from left (smaller subproblems) to right (larger
subproblems). Entry
This way the solution is much more direct.
uint64_t FibonacciIterative(n) {
vector<uint64_t> M(n);
if (n == 0) return 0;
if (n == 1) return 1;
M[0] = 0;
M[1] = 1;
for(size_t i = 2; i < n; ++i)
M[i] = M[i-1] + M[i-2];
return M[n];
}We note that there exist a faster algorithm to compute the $n$th Fibonacci number. Indeed, the $n$th Fibonacci number is the top-left element of the 4x4 matrix
The matrix can be computed in
Serling Enterprises buys long steel rods and cuts them into shorter rods, which it then sells. Each cut is free. The management of Serling Enterprises wants to know the best way to cut up the rods. Given a rod of length $n$ and for any $i\in[1,n]$, the price $p_i$ of a rod of length $i$, the goal is that of determining the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.
The bottom-up DP solution of the problem is as follows.
Our goal is to fill an array
Assuming we have already solved all the subproblems of size
Let's list all the possibilities. We do not cut. The revenue is
Clearly, the value of
A possible implementation of this algorithm is reported below.
uint64_t RodCutting(uint64_t n, vector<uint64_t> &p) {
vector<uint64_t> r(n+1, 0);
for(size_t j = 1; j < n; ++j) {
uint64_t q = 0;
for(size_t i = 1; i < j; ++i)
q = max(q, p[i] + r[j-i]);
r[j] = q;
}
return r[n];
}The algorithm runs in
The algorithm computes only optimal revenue but not a cut that gives such a revenue. The algorithm can be easily modified to obtain a optimal cut. How?
Consider the following running example.
| length | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| price | 0 | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
| revenue | 0 | 1 | 5 | 8 | 10 | 13 | 17 | 18 | 22 | 25 | 30 |
| cut | 0 | 1 | 2 | 3 | 2 | 2 | 6 | 1 | 2 | 3 | 10 |
We are given a matrix $M$ of $n\times m$ integers. The goal is to find the minimum cost path to move from the top-left corner to the bottom-right corner by moving only down or to right.
You can submit your solution here.
Consider the matrix below.
| 1 | 2 | 6 | 9 |
| 0 | 0 | 3 | 1 |
| 1 | 7 | 7 | 2 |
It is easy to see that the following recurrence solves the problem.
[W(i,j) = M[i,j] + \left{ \begin{array}{ll} 0 & \text{if } i = j = 1\ W(i,j-1) & \text{if } i = 1 \text{ and } j > 1\ W(i-1,j) & \text{if } i > 1 \text{ and } j = 1\ \min(W(i-1,j), W(i, j-1))& \text{otherwise}\ \end{array} \right. ]
Thus, the problem is solved in linear time by filling a matrix
| 1 | 3 | 9 | 18 |
| 1 | 1 | 4 | 5 |
| 2 | 8 | 11 | 7 |
Given two sequences $S_1[1,n]$ and $S_2[1,m]$, find the length of longest subsequence present in both of them.
You can submit your solution here.
As an example, consider
The subproblems here ask to compute the LCS of prefixes of the two sequences: given two prefixes
Assume we already know
If
Observe that we could also use
Instead, if
Summarising,
[{\sf LCS}(S_1[1,i], S_2[1,j]) = \left{ \begin{array}{ll} 0 & i = 0 \text{ or } j = 0 \ {\sf LCS}(S_1[1,i-1], S_2[1,j-1]) + 1 & S_1[i]=S_2[j] \ \max({\sf LCS}(S_1[1,i], S_2[1,j-1]), {\sf LCS}(S_1[1,i-1], S_2[1,j])) & \text{otherwise}\ \end{array} \right. ]
Below the pseudocode of this algorithm where we use a matrix
function LCSLength(X[1..m], Y[1..n])
C = array(0..m, 0..n)
for i := 0..m
C[i,0] = 0
for j := 0..n
C[0,j] = 0
for i := 1..m
for j := 1..n
if X[i] = Y[j]
C[i,j] := C[i-1,j-1] + 1
else
C[i,j] := max(C[i,j-1], C[i-1,j])
return C[m,n]
This algorithm runs in
Figure below show the execution of the algorithm on
Take a look to this Wikipedia entry for more details.
Dor is IWGolymp student so he has to count in how many ways he can make binary strings of length $N$ where zeroes cannot be next to each other. Help to him in how many different numbers can he make.
You can submit your solution here.
As an example, if
Let
This problem is similar to the problem of completely covering a 2xn rectangle with 2x1 dominoes. See chapter 7.1 of Concrete Mathematics, 2Ed. by D. Knuth, O. Patashnik, and R. Graham.
We are given $n$ items. Each item $i$ has a value $v_i$ and a weight $w_i$. We need put a subset of these items in a knapsack of capacity $C$ to get the maximum total value in the knapsack.
You can submit your solution here.
The problem is called 0/1 because each item is either selected or not selected. Two possible variants of the problem allows to select fraction of the items (fractional knapsack problem) or select the same item multiple times (0/$\infty$ knapsack problem).
The problem is a well-know NP-Hard problem, which admits a pseudo-polynomial time algorithm.
We can use the following solutions.
- If
$C$ is small, we can use Weight Dynamic Programming. The time complexity is$\Theta(Cn))$ . - Ff
$V=\sum_i v_i$ is small, we can use Price Dynamic Programming. The time complexity is$\Theta(Vn))$ . - If both are large, we can use branch and bound. This approach is not covered by our lecture note.
The idea of the Weight DP algorithm is to fill a
Here an example. Consider a knapsack of capacity
| weight | value |
|---|---|
| 1 | 1 |
| 3 | 4 |
| 4 | 5 |
| 5 | 7 |
The matrix
| value | weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 4 | 3 | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
| 5 | 4 | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
| 7 | 5 | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
The idea of the Profit DP algorithm is similar. We use a
Here you can find more details about this problem.
Given a set $S$ of $n$ non-negative integers, and a value $v$, determine if there is a subset of the given set with sum equal to given $v$.
You can submit your solution here.
The problem is a well-know NP-Hard problem, which admits a pseudo-polynomial time algorithm.
The problem has a solution which is almost the same as 0/1 knapsack problem.
As in the 0/1 knapsack problem, we construct a matrix
Entry
The entries of the first row
Entry
As an example, consider the set
| Elements \ v | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| T | F | F | F | F | F | F | |
| 3 | T | F | F | T | F | F | F |
| 2 | T | F | T | T | F | T | F |
| 5 | T | F | T | T | F | T | F |
| 1 | T | T | T | T | T | T | T |
The algorithm runs in
Here you can find more details about this problem.
We have $n$ types of coins available in infinite quantities where the value of each coin is given in the array $C=[c_1, c_2, \ldots, c_n]$. The goal is find out how many ways we can make the change of the amount $K$ using the coins given.
You can submit your solution here.
For example, if
The solution is similar to the one for 0/1 knapsack and subset sum problems.
The goal is to build a
The easy cases are when
Now, for every coin we have an option to include it in the solution or exclude it.
If we decide to include the $i$th coin, we reduce the amount by coin value and
use the subproblem solution (
If we decide to exclude the $i$th coin, the solution for the same amount without considering that coin is on the entry above.
Given a sequence $S$ of $n$ numbers, find the length of its longest increasing subsequence.
You can submit your solution here.
As an example consider the sequence
Consider the sequence
[{\sf LIS}(i) = \left{ \begin{array}{ll} 1 + \max({\sf LIS}(j) \mid 1 \leq j < i ; \sf {and}; S[j] < S[i])& \ 1 & \text{if such } j \text{ does not exist}\ \end{array} \right. ]
It should be clear that the above recurrence can be solved in
Here you can find more details about this problem.
Often it is convenient to reduce a problem to a (single source) longest path computation on a suitable DAG.
Let's consider again the LIS problem. Our DAG
Edges are as follows. Every vertex has an edge to
By construction, it should be clear that there exists a one-to-one
correspondence between increasing subsequences of
A longest path on a DAG
This reduction is always possible and sometimes it helps in reasoning about properties of the problems to get faster solutions.
Take a look to the tutorial here \url{http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/} for a
Intuition. For any position
We say that position
Considering only dominant positions suffices to find a LIS.
Given a new position
We search for dominant position
We can use a BST to store dominant positions.
For any $r$ and $s$, any sequence $A$ of distinct real numbers with length $n$ at least $(r − 1)(s − 1) + 1$ contains a monotonically increasing subsequence of length $r$ or a monotonically decreasing subsequence of length $s$.
See here for more details.
A proof uses longest increasing subsequence (LIS) and longest decreasing subsequence (LDS) tables built with dynamic programming.
Consider the LIS and LDS tables computed with DP.
For an element of
Consider two positions
- if A[i] < A[j], then
$LIS[j] \geq LIS[i] + 1$ ; - if A[i] > A[j], then
$LDS[i] \geq LDS[j] + 1$ .
As all the pairs are distinct, by Pigeonhole principle, there must be a pair with either a LIS value larger than
Given a sequence $S[1,n]$, find the length of its longest bitonic subsequence. A bitonic sequence is a sequence that first increases and then decreases.
You can submit your solution here.
Consider for example the sequence
The idea is to compute the longest increasing subsequence from left to right and the longest increasing subsequence from right to left by using the
Then, we combine these two solutions to find the longest bitonic subsequence.
This is done by taking the values in a column, adding them and subtracting one.
This is correct because
| S | 2 | -1 | 4 | 3 | 5 | -1 | 3 | 2 |
|---|---|---|---|---|---|---|---|---|
| LIS | 1 | 1 | 2 | 2 | 3 | 1 | 2 | 2 |
| LDS | 2 | 1 | 3 | 2 | 3 | 1 | 2 | 1 |
| LBS | 2 | 1 | 4 | 3 | 5 | 1 | 3 | 2 |
Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element). If an element is $0$, then cannot move through that element.
You can submit your solution here.
As an example, consider the array
Think about the reduction to a SSSP on a DAG. This gives a
A linear time solution is here.
Given a tree $T$ with $n$ nodes, find one of its largest independent sets.
An independent set is a set of nodes
Example below shows a tree whose largest independent set consists of the red nodes a, d, e, and f.
In general the largest independent set is not unique. For example, we can obtain a different largest independent set by replacing nodes a and d with nodes b and g.
Consider a bottom up traversal of the tree
In the former case,
Let
Thus, we have the following recurrence. [{\sf LIST}(u) = \left{ \begin{array}{ll} 1 & \text{if } u \text{ is a leaf}\ \max(1 + \sum_{v \in G_u}{\sf LIST}(v), \sum_{v \in C_u}{\sf LIST}(v))& \text{otherwise}\ \end{array} \right. ]
The problem is, thus, solved with a post-order visit of
Observe that the same problem on general graphs is NP-Hard.
Given two strings $S_1[1,n]$ and $S_2[1,m]$, find the minimum number of edit operations required to transform $S_1$ into $S_2$. There are three edit operations:
- Insert a symbol at a given position
- Replace a symbol at a given position
- Delete a symbol at a given position.
You can submit your solution here.
For example, if the two strings are
Let
[{\sf ED}(i,j) = \left{
\begin{array}{ll}
i & \text{if }
Here we report the matrix obtained for the strings
| ∅ | a | b | c | d | e | f | |
|---|---|---|---|---|---|---|---|
| ∅ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| a | 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| g | 2 | 1 | 1 | 2 | 3 | 4 | 5 |
| c | 3 | 2 | 2 | 1 | 2 | 3 | 4 |
| e | 4 | 3 | 3 | 2 | 2 | 2 | 3 |
| d | 5 | 4 | 4 | 3 | 2 | 3 | 3 |
Here you can find more details about this problem.
Given a sequence $S[1,n]$, find the length of its longest palindromic subsequence.
You can submit your solution here.
Given sequence is
Let
There is a very easy solution which reduces to the Longest Common Subsequence Problem.
Indeed, it is easy to see that the longest common subsequence of
A direct computation of the longest palindromic subsequence is based on the idea
of computing
Thus, the recurrence is as follows.
[{\sf LPS}(i,j) = \left{
\begin{array}{ll}
0 & \text{if }
Here we report the matrix obtained for the example above. Observe that we have to fill the matrix starting from its diagonal
| b | b | a | b | c | b | c | a | b | |
|---|---|---|---|---|---|---|---|---|---|
| b | 1 | 2 | 2 | 3 | 3 | 5 | 5 | 5 | 7 |
| b | 0 | 1 | 1 | 3 | 3 | 3 | 3 | 5 | 7 |
| a | 0 | 0 | 1 | 1 | 1 | 3 | 3 | 5 | 5 |
| b | 0 | 0 | 0 | 1 | 1 | 3 | 3 | 3 | 5 |
| c | 0 | 0 | 0 | 0 | 1 | 1 | 3 | 3 | 3 |
| b | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 3 |
| c | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| a | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| b | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
There are $n$ jobs and three arrays $S[1\ldots n]$ and $F[1\ldots n]$ listing the start and finish times of each job, and $P[1\ldots n]$ reporting the profit of completing each job. The task is to choose a subset $X \subseteq {1, 2, \ldots, n}$ so that for any pair $i,j \in X$, either $S[i] > F[j]$ or $S[j] > F[i]$, which maximizes the total profit.
Consider the following example. Arrays are
The solution is as follows. We first sort the jobs by finish time.
Let
The value of
We assume we have a fake job with index
Observe that sorting by finish time guarantees that if we current job
Notice that the index
| S | - | 1 | 2 | 4 | 6 | 5 | 7 |
|---|---|---|---|---|---|---|---|
| F | 3 | 5 | 6 | 7 | 8 | 9 | |
| P | 0 | 5 | 6 | 5 | 4 | 11 | 2 |
| R | 0 | 5 | 6 | 10 | 14 | 17 | 17 |
We notice that this problem under the hypothesis that all the jobs have the same profit is called activity selection. For that easier problem, a greedy algorithm finds the optimal schedule in
A coin is tossed $n$ times. Find the number of combinations such that there is no $3$ consecutive tails.
You can submit your solution here.
We use a
For each position
-
$dp[i][0]$ is the number of combinations for$i$ tosses that ends with head -
$dp[i][1]$ is the number of combinations for$i$ tosses that ends with a tail preceded by head -
$dp[i][2]$ is the number of combinations for$i$ tosses that ends with two tails preceded by head.
The result is
How do we compute
We have
$dp[1][0] = 1$ $dp[1][1] = 1$ $dp[1][0] = 0$
For a generic position
- We put a head in position
$i$ . In this case we have$dp[i][0] = dp[i-1][0]+dp[i-1][1]+dp[i-1][2]$ . - We put a tail in position
$i$ . In this case we have$dp[i][1] = dp[i-1][0]$ and$dp[i][2] = dp[i-1][1]$ .
There are two players: Alice and Bob. We have an even number $n$ of coins of different values in a row. First Alice picks up a coin from one of the ends. Then, Bob takes a coins from one of the (new) ends, and so on. The game ends when Bob takes the last coin. Is there any stategy for Alice which always guarantes Alice to get at least as much money as Bob?
This puzzle is described in Mathematical Puzzles by Peter Winkler.
Consider coins at even positions and coins at odd positions. As there is a even number of coins and Alice starts first, she can always choose to get all coins at even positions or all coins at odd positions. Thus, she simply chooses even or odd depending on which gives the best result.
Notice that this strategy always works, no matter the values of the coins.
Moreover, there no possible strategy when the number of coins is odd.
For example, if we have three coins
We are playing the same game before. Given the $n$ coins $A[1,n]$, we want to maximize the difference between coins taken by Alice and the ones of Bob. We assume that both players play optimally.
Let be
[{\sf dp}(i,j) = \left{
\begin{array}{ll}
0 & \text{if }
Here is an example.
| 10 | 1 | 3 | 5 | 1 | 7 | |
|---|---|---|---|---|---|---|
| i/j | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 10 | 10-1 = 9 | 10-2 = 8 | 10-3 = 7 | 10-2=10 | 10-5=5 |
| 2 | 0 | 1 | 3-1 = 2 | 5-2 = 3 | 1+1 = 2 | 7-2=5 |
| 3 | 0 | 0 | 3 | 5-3 = 2 | 3-4=-1 | 7+1 = 8 |
| 4 | 0 | 0 | 0 | 5 | 5-1 = 4 | 7-4 = 3 |
| 5 | 0 | 0 | 0 | 0 | 1 | 7-1 = 6 |
| 6 | 0 | 0 | 0 | 0 | 0 | 7 |
You are given an integer array $a_1, a_2, \ldots, a_n$. The array $b$ is called to be a subsequence of $a$ if it is possible to remove some elements from $a$ to get $b$.
Array $b_1, b_2, \ldots, b_k$. is called to be good if it is not empty and for every $j$ ($1\leq j \leq k$) $b_j$ is divisible by $j$.
Find the number of good subsequences in $a$ modulo $10^9+7$.
The value of
You can submit your solution here
We use
This solution would require
To reduce the space use, we notice that we do not need to use a 2D matrix but we can simply use a vector to store only the last column of
To reduce the time, we observe that we only need to update rows corresponding to indexes
We are given an array $A[1,n]$ and an integer $K$. The goal is to count the number of subsequence of $A$ of length $3$ form a geometric progression with ratio $K$. A geometric progression with ratio $K$ is $b, bK^0, bK^1, bK^2, \ldots$
You can submit your solution here
For every entry
These numbers can be computed as follows:
-
$N[i,1] = N[j,1]+1$ , where$j<i$ is the largest position such that$A[j]=A[i]$ ; -
$N[i,2] = N[j,2] + N[j',1]$ , where$j$ is as before and$j'<i$ is the largest position such that$A[j]=A[i]/K$ ; -
$N[i,3] = N[j,3] + N[j',2]$ , where$j$ and$j'$ are as before.$c += N[j',2]$ .
Notice, that instead of computing positions
This solution can be easily generalised to solve the same problem with longer subsequences.
An easier solution that works for length