RADIM URBAN

Dynamic Programming Collection

Jan 22, 2022

About

I decided to summarize the DP exercises from the first semester (and add some more), so that I have better overview of them. I will improve this blog-post over time (comment the code, explain the approach, add more problems). Right now, it really is only an overview.


Travelling Salesman Problem [xkcd]

There are following DP problems so far:

Longest Positive Subsequence

Task

The task is to program an algorithm that for an array, computes the length of its longest positive subarray, where a subarray is called positive if all its elements are positive. For example, the longest posistive subarray of the array \(A = \{1,-1,3,2,5,-4,5\}\) is \( \{3,2,5\} \), and its length is \( 3 \).

Solution

The approach here is to keep track of the longest positive subsequence at each point of the array. Formally that is for an array element \( a_i \) the number \(max_i \) is a length of the longest positive subsequence of the array \(A[1..i] \).
Than we define the recursion as follows: \[ counter[i] = \begin{cases} 1 & \mbox{if } i=0 \mbox{ and } A[i] >0 \\ 0 &\mbox{if } A[i] \leq 0\\ counter[i-1]+1 & \mbox{otherwise} \\ \end{cases} \] and the \(max\) like this: \[ max[i] = max \begin{cases} counter[i] \\ max[i-1] & \mbox{for } i>0 \end{cases} \] We additionally define the variable \(max\) to keep track of the biggest \(counter\) so far. At the end we return the \(max\). The table would look like this: \[ \begin{array} {|l|c|} \hline \textbf{A} & 1 & -1 & 3 & 2 & 5 & -4 & 5 \\ \hline \textbf{max} & 1 & 1 & 1 & 2 & 3 & 3 & \color{#bf2a2a}{\textbf{3}} \\ \hline \textbf{counter} & 1 & 0 & 1 & 2 & 3 & 0 & 1 \\ \hline \end{array} \] \[\mbox{Table of DP entries.} \] The running time is \(\mathcal{O}(n)\).

Implementation

Energy for a Trip

Task

Your task is to program an algorithm that computes the minimum energy to complete a trip. More formally, you need to compute the minimum energy for moving from position \(0\) to position \(n\) . There are walls in some positions, and you can using the following three ways to move.

For example, if you are in Position 5, Positions 6-10 are walls, but Position 11 is NOT a wall, the you can use Jump.
The input is a Boolean array A: for \(1\leq i\leq n\), if \(A[i]=1\), Position \(i\) is a wall, and if \(A[i]=0\), Position is Not a Wall.

Solution

At the very beginning the cost is clearly \(0\) as we do not need to move. This is our base case. After that we move based on if there is wall or not. If there is wall at position \(i\), we have to climb the wall which costs \(2\). If position \(i\) is not a wall, based on whether we already are at position \(i\geq5\) we take the cheaper out of these two options: We either move back by 6 positions and jump forward again (with the cost of \(8\) and only applicable in case \(i\geq5\)) or simply move forward with cost of \(1\).
Formally, we can say: \[ dp(i) = \begin{cases} 0 & \mbox{if } i=0, \\ dp(i-1) + 2 & \mbox{road[i] = true,} \\ min \begin{cases} dp(i-1)+1 \\ dp(i-6)+8 \end{cases} & \mbox{road[i] = false and } i>5, \\ dp(i-1)+1 & \mbox{otherwise.} \end{cases} \]

The DP table could then look like this:
\[ \begin{array} {|l|c|} \hline \textbf{i} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \textbf{road} & - & \mbox{true} & \mbox{false} & \mbox{false} & \mbox{true} & \mbox{true} & \mbox{false} & \mbox{true} & \mbox{true} & \mbox{false} & \mbox{true} \\ \hline \textbf{dp} & 0 & 2 & 3 & 4 & 6 & 8 & 8 & 10 & 12 & 12 & \color{#bf2a2a}{\textbf{14}} \\ \hline \end{array} \] \[\mbox{Table of DP entries.} \] The running time is \(\mathcal{O}(n)\).

Implementation

Maximizing an Expression

Task

The task is to program an algorithm that computes the maximum value of a given expression by inserting parentheses.
More formally, for an arithmetic expression containing n integers and \(n-1\) operators each which is either \(+\) or \(\cdot\), the goal is to maximize the value of the expression by inserting parentheses.
For instance, if the expression is \(7 + 4 + (-3) \cdot 6 + (-5)\), the maximum value is attained by \((((7 + 4) + (- 3)) \cdot 6) + (-5) = 43\).
Your solution has to be in \(\mathcal{O}(n^3)\) time, where n is the number of integers in the expression.

Hint: You may require two tables, one for the maximum values and one for the minimum values. In particular, completing either table requires the other table.

Attention: You need to be very careful about how the signs affect the recursion. For example, if you multiply numbers from intervals \([a,b]\) and \([c,d]\), then the maximum possible value of the product is \(b \cdot d\) if all values \(a,b,c,d\) are positive. But the maximum is \(a \cdot c\) if all values are negative, and it might also be \(b \cdot c\) or \(a \cdot d\) in other cases.

Solution

We use two DP tables to construct the final result, one keeping track of the smallest possible values and one for the biggest possible values. We deal with every single possible value coming out for patricular sign at every point. Then the smallest and biggest possible outcomes are saved into the respective DP table.
For example \(7 + 4 + (-3) \cdot 6 + (-5)\), the two corresponding DP tables would look like this: \[ \begin{array} {|c|c|} \hline \textbf{MinTB} & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} \\ \hline \textbf{0} & 7 & 11 & 8 & -7 & -12 \\ \hline \textbf{1} & \mbox{Integer.MAX_VALUE} & 4 & 1 & -14 & -19 \\ \hline \textbf{2} & \mbox{Integer.MAX_VALUE} & \mbox{Integer.MAX_VALUE} & -3 & -18 & -23 \\ \hline \textbf{3} & \mbox{Integer.MAX_VALUE} & \mbox{Integer.MAX_VALUE} & \mbox{Integer.MAX_VALUE} & 6 & 1 \\ \hline \textbf{4} & \mbox{Integer.MAX_VALUE} & \mbox{Integer.MAX_VALUE} & \mbox{Integer.MAX_VALUE} & \mbox{Integer.MAX_VALUE} & -5 \\ \hline \end{array} \] \[\mbox{The DP table of minimal possible outcomes}\] \[ \begin{array} {|c|c|} \hline \textbf{MaxTB} & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} \\ \hline \textbf{0} & 7 & 11 & 8 & 48 & \textbf{43} \\ \hline \textbf{1} & \mbox{Integer.MIN_VALUE} & 4 & 1 & 6 & 1 \\ \hline \textbf{2} & \mbox{Integer.MIN_VALUE} & \mbox{Integer.MIN_VALUE} & -3 & -18 & -3 \\ \hline \textbf{3} & \mbox{Integer.MIN_VALUE} & \mbox{Integer.MIN_VALUE} & \mbox{Integer.MIN_VALUE} & 6 & 1 \\ \hline \textbf{4} & \mbox{Integer.MIN_VALUE} & \mbox{Integer.MIN_VALUE} & \mbox{Integer.MIN_VALUE} & \mbox{Integer.MIN_VALUE} & -5 \\ \hline \end{array} \] \[\mbox{The DP table of maximal possible outcomes}\] Note also that we only need to fill the upper triangular matrix to get to the result. The \(\mathcal{O}(n^3)\)implementation:

Implementation

Shortest Common Supersequence

Program an algorithm that computes the length of the shortest common supersequence between two given seqeuences.
More formally, for an \(n\)-element sequence \(A\) and an \(m\)-element sequence \(B\), the shortest common supersequence between \(A\) and \(B\) is the shortest sequence \(C\) such that both \(A\) and \(B\) are a subsequence of \(C\).

DNA Sequence Alignment

A DNA sequence is a string of characters from a four-character alphabet \(\{A, T, G,C\}\). For a pair of two strings \(x\) and \(y\), an alignment is given by inserting gaps into both \(x\) and \(y\) at arbitrary places until they have the same length. Each insertion of a gap costs \(2\). Afterwards, for each position, we have an additional cost of \(1\) for each position in which the extended strings do not match. Thus the aligning operations and their costs are:

Your task is to compute the minimal cost \(c\) of aligning two DNA sequences \(x\) and \(y\). Note that length of \(x\) does not have be the same as length of \(y\).
Let \(dp[i][j]\) denote the cost of aligning the strings \(x[0..i]\) and \(y[0...j]\). The DP will work as follows: \[ dp[i][j] = \begin{cases} 2 \cdot i & \mbox{if } j = 0 \\ 2 \cdot j & \mbox{if } i = 0 \\ min \begin{cases} dp[i-1][j-1] + \begin{cases} 0 & \mbox{if } x[i] == y[j] \\ 1 & \mbox{otherwise} \end{cases} \\ dp[i-1][j]+2 \\ dp[i][j-1]+2 \end{cases} \end{cases} \] We then extract the solution from \(dp[\mbox{x.length()}][\mbox{y.length()}]\).
The DP table for \(x =\) "TGACA" and \(y =\) "GACCA" yields the result \(3\) and looks like this: \[ \begin{array} {|c|c|} \hline \textbf{DP} & \textbf{-} & \textbf{T} & \textbf{G} & \textbf{A} & \textbf{C} & \textbf{A} \\ \hline \textbf{-} & 0 & 2 & 4 & 6 & 8 & 10 \\ \hline \textbf{G} & 2 & 1 & 3 & 5 & 7 & 9 \\ \hline \textbf{A} & 4 & 2 & 2 & 4 & 6 & 8 \\ \hline \textbf{C} & 6 & 4 & 2 & 3 & 5 & 6 \\ \hline \textbf{C} & 8 & 6 & 4 & 2 & 3 & 5 \\ \hline \textbf{A} & 10 & 8 & 6 & 4 & 3 & \color{#bf2a2a}{\textbf{3}} \\ \hline \end{array} \] \[ \mbox{Table of DP entries.} \] This solution works in \(\mathcal{O}(x\mbox{.length()} \cdot y\mbox{.length()})\).

Square (Find biggest square 1 matrix)

You are given a 2-dimensional binary matrix \(B\) having \(M\) rows and \(N\) columns filled with only 0's and 1's. Your task is to find the area of a largest square submatrix that contains only 1's.

Longest Alternating Subarray

The task is to program an algorithm that, for an array of distinct integers, computes the length of its longest alternating subarray. A subarray is called alternating if its values form a zig-zag pattern. More precisely, for a subarray, write down comparison signs (< and >) between its elements. Then, the subarray is called alternating if the comparison signs form a sequence \((<, >, <, >, ...)\) or \((>, <, >, <, ...)\) .

To illustrate, consider the subarray \(\{1, 5, 3, 4, 2, 6\} \) . Then the comparison signs are \((<, >, <, >, <)\) , so the subarray is alternating. On the other hand, consider the subarray \(\{1, 5, 3, 4, 6, 2\}\) . Then the comparison signs are \((<, >, <, <, >)\) , so the subarray is not alternating.

As a final example, for the array \(\{1, 9, 2, 3, 5, 4, 6, 7, 8\}\) , the longest alternating subarray has length \(4\) and corresponds to either \(\{1, 9, 2, 3\}\) or \(\{3, 5, 4, 6\}\) .

Palindromic Distance

Given a sequence \(A\) of \(n\) characters, your task is to compute the minimum number of operations that is required to turn \(A\) into a palindrome. We consider the following operations:

Let \(dp(i,j)\) denote the minimum number of operations to convert substring \(s[i...j]\) into palindrome. More formally, for string \(s\), the palindromic distance is: \[ dp(i,j) = \begin{cases} \mbox{0} & \mbox{if } i \geq j \\ \mbox{dp(i+1, j-1)} & \mbox{if } s[i] == s[j] \\ \mbox{1 + min} \begin{cases} \mbox{dp(i+1, j-1)} & \mbox{(1)} \\ \mbox{dp(i+1, j)} & \mbox{(2)} \\ \mbox{dp(i, j-1)} & \mbox{(3)} \end{cases} \end{cases} \] The operations \( (1), (2), (3)\) correspond to following operations:

\((1)\) - replace characters of \(s[i]\) to \(s[j]\) or \(s[j]\) to \(s[i]\)
\((2)\) - remove \(i\)-th character or insert a new character right after \(j\)-th position
\((3)\) - remove \(j\)-th character or insert a new character right before \(i\)-th position

For example, if \(s\) is "ETHZETHZ", the answer is \(3\). \[ \begin{array} {|c|c|} \hline \textbf{DP} & \textbf{E} & \textbf{T} & \textbf{H} & \textbf{Z} & \textbf{E} & \textbf{T} & \textbf{H} & \textbf{Z} \\ \hline \textbf{E} & 0 & 1 & 1 & 2 & 1 & 2 & 2 & \color{#bf2a2a}{\textbf{3}} \\ \hline \textbf{T} & 0 & 0 & 1 & 1 & 2 & 1 & 2 & 2 \\ \hline \textbf{H} & 0 & 0 & 0 & 1 & 1 & 2 & 1 & 2 \\ \hline \textbf{Z} & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 1 \\ \hline \textbf{E} & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \hline \textbf{T} & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline \textbf{H} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \hline \textbf{Z} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array} \] \[ \mbox{DP table entries. The result is at dp[0][n-1].} \]

Shuffle

Given three strings \(A, B, C\) with \(|A|=n, |B|=m , |C|=n+m\) , your task is to decide if \(C\) is a shuffle of \(A\) and \(B\). A shuffle of \(A\) and \(B\) is formed by merging \(A\) and \(B\) into a new string while maintaining both the internal order of the characters of \(A\) and the internal order of the characters of \(B\) . For example, \(C =\) PINEAPPLE is a shuffle of \(A =\) PAPLE and \(B = \) INEP.

Longest Palindromic Subsequence

Given a sequence \(A\) of \(n\) characters, your task is to compute the length of the longest palindromic subsequence of \(A\) , i.e., the length of the longest subsequence of \(A\) that is a palindrome.

For instance, if \(A\) is "ETHZEBEHU", "HEBEH" is the longest palindromic subsequence of \(A\) , and its length is \(5\). \[ \begin{array} {|c|c|} \hline \textbf{DP} & \textbf{E} & \textbf{T} & \textbf{H} & \textbf{Z} & \textbf{E} & \textbf{B} & \textbf{E} & \textbf{H} & \textbf{U} \\ \hline \textbf{E} & \textbf{1} & 1 & 1 & 1 & 3 & 3 & 3 & 5 & \color{#BF2A2A}{\textbf{5}} \\ \hline \textbf{T} & 0 & \textbf{1} & 1 & 1 & 1 & 1 & 3 & 5 & 5 \\ \hline \textbf{H} & 0 & 0 & \textbf{1} & 1 & 1 & 1 & 3 & 5 & 5 \\ \hline \textbf{Z} & 0 & 0 & 0 & \textbf{1} & 1 & 1 & 3 & 3 & 3 \\ \hline \textbf{E} & 0 & 0 & 0 & 0 & \textbf{1} & 1 & 3 & 3 & 3 \\ \hline \textbf{B} & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 1 & 1 & 1 \\ \hline \textbf{E} & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 1 & 1 \\ \hline \textbf{H} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} & 1 \\ \hline \textbf{U} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \textbf{1} \\ \hline \end{array} \\ \] \[ \mbox{Table showing the entries of the DP table. The result is at dp[0][n-1] and the base cases are in } \textbf{bold}.\] The running time should be \( \mathcal{O}(n^2)\).

Art Gallery

A gang of thieves is robbing an art gallery. They own a truck with a volume of \(V\) which they plan to fill with valuable sculptures. There are \(n\) sculptures in the gallery, the \(n\)-th of which is guarded by a sophisticated alarm system that requires \(t \geq 0\) minutes to disable. The \(i\)-th sculpture has a value \(p_i > 0\) on the black market and occupies \(v_i > 0\) in the truck.

The thieves only have \(T\) minutes before the police arrives. The task is to design an algorithm that computes the maximum amount of money they can make form the heist.

The program should run in time \( \mathcal{O}(nVT) \) with reasonable hidden constants).

Partition of an Array

You are given an array of \(n\) natural numbers \( a_1,...,a_n \in \mathbb{N}\) summing to \(A\), which is a multiple of \(3\).
You want to determine whether it is possible to partition \(\{1, . . . , n\}\) into three disjoint subsets \(I, J, K\) such that the corresponding elements of the array yield the same sum, that is \(|I| = |J| = |K| = \frac{A}{3}\).

For example, the answer for the input \(\{2,4,8,1,4,5,3\}\) is yes, because there is the partition \((3,4), (2,6), (1,5,7)\) (corresponding to the subarrays \(\{8,1\}, \{4,5\}, \{2,4,3\}\), which are all summing to \(9\)). On the other hand, the answer for the input \(\{3,2,5,2\}\) is no. Provide a dynamic programming algorithm that determines whether such a partition exists.
Your algorithm should have an \( \mathcal{O}(nA^2)\) runtime.

Grid Traversal

Given is a square grid of size \(N\times N\). Rows and columns are indexed from \(0\) to \(N-1\) and each cell at index (row, column) contains a positive value (its cost) as shown in the example below. You are asked to traverse the grid from the top row to the bottom row, one row at a time. In each step, you can move from a cell \((i,j)\) in row \(i\) to either of the cells \((i + 1, j -1)\), \((i + 1, j)\), or \((i + 1; j + 1)\) in row \(i + 1\). As start you can pick any cell in the first row.
The overall cost of a traversal is the sum of the costs of all visited cells, including start and end.

Devise an algorithm to find a path from top to bottom of the grid that minimizes the overall traversal cost.
The algorithm should work in \( \mathcal{O}(N^2) \).

Levenshtein (Edit) Distance

Levenshtein distance is a string metric for measuring the difference between two sequences.
Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other.
The expected runtime is \( \mathcal{O}(|a|\cdot|b|) \).

More formally, for two strings \(a\) and \(b\), the Leveshtein (Edit) Distance is: \[ dp(i,j) = \begin{cases} \mbox{i} & \mbox{if } j==0 \\ \mbox{j} & \mbox{if } i==0 \\ \mbox {dp(i-1, j-1)} & \mbox{if } a[i] == a[j] \\ \mbox{1+min} \begin{cases} \mbox{dp(i-1, j)} \\ \mbox{dp(i, j-1)} \\ \mbox{dp(i-1, j-1)} \end{cases} & \mbox{otherwise} \end{cases} \]
Example: For strings \(a = \) "OTTAWA" and \(b = \) "ORLOVA", the result is \(4\) and we would get following DP table: \[ \begin{array} {|c|c|} \hline \textbf{DP} & \textbf{-} & \textbf{O} & \textbf{T} & \textbf{T} & \textbf{A} & \textbf{W} & \textbf{A} \\ \hline \textbf{-} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \textbf{O} & 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline \textbf{R} & 2 & 1 & 1 & 2 & 3 & 4 & 5 \\ \hline \textbf{L} & 3 & 2 & 2 & 2 & 3 & 4 & 5 \\ \hline \textbf{O} & 4 & 3 & 3 & 3 & 3 & 4 & 4 \\ \hline \textbf{V} & 5 & 4 & 4 & 4 & 4 & 4 & 5 \\ \hline \textbf{A} & 6 & 5 & 5 & 5 & 5 & 5 & \color{#BF2A2A}{\textbf{4}} \\ \hline \end{array} \] \[\mbox{Table with the DP entries.}\] Code implementation:

Is A and B particular sum of array elements?

Given is an array \(X\) with \(n\) elements \((x_1 ,... , x_n)\). Additionally, two numbers \(A\) and \(B\) are given. We want to find out if \(A\) is a sum of elements in \(X\) and \(B\) is a sum of elements squared and in \(X\).
Formally, we want to know, if \( A = \sum_{i=1}^{n} (x_i) \) and \( B = \sum_{i=1}^{n} (x_i^2) \) is true.
Let's define the \(dp\) table with dimension \((n+1) \times (A+1) \times (B+1)\) and the recursion as follows: \[ dp[i][j][k] = \begin{cases} \mbox{true} & \mbox{if } i=j=k=0 \\ \mbox{false} & \mbox{if } i=0 \mbox{ and } i \neq j \mbox{ and } i \neq k \\ dp[i-1][j][k] \mbox{ or } dp[i-1][j-x_i][k-x_i^2] & \mbox{otherwise} \end{cases} \] We can implement this in \(\mathcal{O}(nAB)\). The solution is at \(dp[n][A][B]\).