Dynamic Programming

Prev: Recursion Next: Greedy Algorithms and Invariants

Problems

17.1

In an American football game, a play can lead to 2 points (safety), 3 points (field goal), or 7 points (touchdown, assuming the extra point). Many different combinations of 2-, 3-, and 7-point plays can make up a final score. For example, there are four combinations of plays that yield a score of 12:

6 safeties
3 safeties and 2 field goals
1 safety, 1 field goal, and 1 touchdown
4 field goals

Write a program that takes a final score and scores for individual plays, and returns the number of combinations of plays that result in the final score.

Hint: Count the number of combinations in which there are $0$ plays of one type, then $1$ , and so on.

Variant: Solve the same problem using $O (s)$ space.

Variant: Return the number of scoring sequences of plays that result in the final score. For example, 18 sequences of plays yield a score of 12.

Variant: Suppose the final score is given as $(s, s^{'})$ , i.e., Team 1 scored $s$ points and Team 2 scored $s^{'}$ points. Compute the number of distinct scoring sequences that result in this score.

Variant: Suppose the final score is $(s, s^{'})$ . Compute the maximum number of lead changes that could have occurred.

Variant: You are climbing stairs. You can advance $1$ to $k$ steps at a time, and your destination is exactly $n$ steps up. Compute the number of ways to reach the top.

17.2

Spell checkers make suggestions for misspelled words. Vladimir Levenshtein defined the distance between two words as the minimum number of edits required to transform the first into the second, where one edit is an insertion, deletion, or substitution of a single character. For example, the Levenshtein distance between "Saturday" and "Sundays" is 4.

Write a program that takes two strings and computes the minimum number of edits needed to transform the first string into the second.

Hint: Consider the same problem for prefixes of the two strings.

Variant: Compute the Levenshtein distance using $O (min (a, b))$ space and $O (ab)$ time.

Variant: Given $A$ and $B$ , compute a longest common subsequence of $A$ and $B$ .

Variant: Given a string $A$ , compute the minimum number of characters you need to delete from $A$ to make the resulting string a palindrome.

Variant: Given a string $A$ and a regular expression $r$ , find the string in the language of $r$ that is closest to $A$ under Levenshtein distance.

Variant: Define a string $t$ to be an interleaving of strings $s_{1}$ and $s_{2}$ if its characters can be formed by interleaving the characters of $s_{1}$ and $s_{2}$ while preserving the left-to-right order of each. Given $s_{1}$ , $s_{2}$ , and $t$ , determine if $t$ is an interleaving of $s_{1}$ and $s_{2}$ .

17.3

Count the number of ways to start at the top-left corner of a 2D array and get to the bottom-right corner, moving only right or down. For example, a $5 \times 5$ array has 70 such paths.

Write a program that counts how many ways you can go from the top-left to the bottom-right in a 2D array.

Hint: If $i > 0$ and $j > 0$ , you can get to $(i, j)$ from $(i - 1, j)$ or $(i, j - 1)$ .

Variant: Solve the same problem using $O (min (n, m))$ space.

Variant: Solve the same problem in the presence of obstacles, specified by a Boolean 2D array, where a true value represents an obstacle.

Variant: A fisherman is in a rectangular sea. The value of the fish at point $(i, j)$ is specified by an $n \times m$ 2D array $A$ . The fisherman can only move down or right. Compute the maximum value of fish that can be caught on a path from the upper-leftmost point to the lower-rightmost point.

Variant: Solve the same fisherman problem when the fisherman can begin and end at any point, but must still move only down or right. The value at $(i, j)$ may be negative.

Variant: A decimal number is a sequence of digits over ${0, 1, 2, \dots, 9}$ of length at least 1, whose first digit cannot be 0. Call a decimal number $D$ monotone if $D [i] \leq D [i + 1]$ for all valid $i$ . Given a positive integer $k$ , compute the number of decimal numbers of length $k$ that are monotone.

Variant: Define strictly monotone similarly, but require $D [i] < D [i + 1]$ . Compute the number of strictly monotone decimal numbers of length $k$ .

17.4

The binomial coefficient $(k n)$ is the number of ways to choose a $k$ -element subset from an $n$ -element set. Direct computation from the factorial formula can overflow in intermediate steps even when the final answer fits in an integer word.

Design an efficient algorithm for computing $(k n)$ with the property that it never overflows if the final result fits in the integer word size.

Hint: Write an equation.

17.5

Suppose you are given a 2D array of integers (the “grid”), and a 1D array of integers (the “pattern”). The pattern occurs in the grid if it is possible to start from some entry in the grid and traverse adjacent entries in the order specified by the pattern until all entries in the pattern have been visited. Adjacent entries are directly above, below, left, or right. It is acceptable to visit an entry in the grid more than once.

For example, if the grid is

135246357

and the pattern is $⟨ 1, 3, 4, 6 ⟩$ , then the pattern occurs in the grid, but $⟨ 1, 2, 3, 4 ⟩$ does not.

Write a program that takes a 2D array and a 1D array, and checks whether the 1D array occurs in the 2D array.

Hint: Start with length-1 prefixes of the 1D array, then move on to longer prefixes.

Variant: Solve the same problem when you cannot visit an entry in the grid more than once.

Variant: Enumerate all solutions when you cannot visit an entry in the grid more than once.

17.6

A thief breaks into a clock store. Each clock has an integer weight and an integer value. The thief’s knapsack can hold no more than a specified combined weight, and the goal is to choose clocks whose total value is maximum subject to the weight constraint.

Write a program for the knapsack problem that selects a subset of items with maximum value and satisfies the weight constraint. Return the value of the subset.

Hint: Greedy approaches are doomed.

Variant: Solve the same problem using $O (w)$ space.

Variant: Solve the same problem using $O (C)$ space, where $C$ is the number of achievable weights between 0 and $w$ .

Variant: Solve the fractional knapsack problem, where the thief may take a fractional part of an item.

Variant: In the divide-the-spoils-fairly problem, two thieves want to divide the stolen items into two groups so that the difference between the values of the two groups is minimized. Solve this problem.

Variant: Solve the divide-the-spoils-fairly problem with the additional constraint that the thieves must receive the same number of items.

Variant: The members of the Electoral College cast their vote for the same candidate within each state. Determine whether a tie is possible in a US presidential election with two candidates, given the number of electors for each state and Washington, D.C.

17.7

Suppose you are designing a search engine. In addition to getting keywords from a page’s content, you would like to get keywords from URLs. For example, bedbathandbeyond.com yields the keywords "bed", "bath", "beyond", "bat", "hand" from the decompositions "bed bath beyond" and "bed bat hand beyond".

Given a dictionary, i.e., a set of strings, and a name, design an efficient algorithm that checks whether the name is the concatenation of a sequence of dictionary words. If such a concatenation exists, return it. A dictionary word may appear more than once in the sequence.

For example, "a", "man", "a", "plan", "a", "canal" is a valid decomposition for "amanaplanacanal".

Hint: Solve the generalized problem: for each prefix of the name, determine whether it is the concatenation of dictionary words.

Variant: Palindromic decompositions were described in Problem 16.7. Every string has a trivial palindromic decomposition into single characters. For example, the minimum palindromic decomposition of "0204451881" is "020", "44", "5", "1881". Compute a palindromic decomposition of a string that uses a minimum number of substrings.

17.8

A sequence of integer arrays in which the $n$ th array consists of $n$ entries naturally corresponds to a triangle of numbers.

Define a path in the triangle to be a sequence of entries in which adjacent entries in the sequence correspond to adjacent entries in the triangle. The path must start at the top, descend continuously, and end at an entry on the bottom row. The weight of a path is the sum of its entries.

Write a program that takes as input a triangle of numbers and returns the weight of a minimum weight path.

Hint: What property does the prefix of a minimum weight path have?

17.9

In the pick-up-coins game, an even number of coins are placed in a line. Two players take turns choosing one coin each, but may only choose from the two coins at the ends of the line. The game ends when all coins have been picked up. The player whose coins have the higher total value wins, and a player cannot pass.

Design an efficient algorithm for computing the maximum total value for the starting player in the pick-up-coins game.

Hint: Relate the best play for the first player to the best play for the second player.

17.10

You are climbing stairs. You can advance $1$ to $k$ steps at a time. Your destination is exactly $n$ steps up.

Write a program which takes as inputs $n$ and $k$ and returns the number of ways in which you can get to your destination. For example, if $n = 4$ and $k = 2$ , there are five ways.

Hint: How many ways are there in which you can take the last step?

17.11

Consider the problem of laying out text using a fixed-width font. Each line can hold no more than a fixed number of characters, and words on a line are separated by exactly one blank. This can leave whitespace at the end of a line.

Define the messiness of a single line ending with $b$ blank characters to be $b^{2}$ . The total messiness of a sequence of lines is the sum of the messinesses of all lines.

Given text, i.e., a string of words separated by single blanks, decompose the text into lines such that no word is split across lines and the messiness of the decomposition is minimized. Each line can hold no more than a specified number of characters.

Hint: Focus on the last word and the last line.

Variant: Solve the same problem when the messiness is the sum of the messinesses of all but the last line.

Variant: Suppose the messiness of a line ending with $b$ blank characters is defined to be $b$ instead of $b^{2}$ . Can you solve the messiness minimization problem in $O (n)$ time and $O (1)$ space?

17.12

The problem of finding the longest nondecreasing subsequence in a sequence of integers has applications in string matching and card games. For example, for the array in Figure 17.15, the length of a longest nondecreasing subsequence is 4. There are multiple such subsequences, e.g., $⟨ 0, 4, 10, 14 ⟩$ and $⟨ 0, 2, 6, 9 ⟩$ .

Write a program that takes as input an array of numbers and returns the length of a longest nondecreasing subsequence in the array.

Hint: Express the longest nondecreasing subsequence ending at an entry in terms of the longest nondecreasing subsequence appearing in the subarray consisting of preceding elements.

Variant: Return a longest nondecreasing subsequence, not just its length.

Variant: Define a sequence $⟨ a_{0}, a_{1}, \dots, a_{n - 1} ⟩$ to be alternating if $a_{i} < a_{i + 1}$ for even $i$ and $a_{i} > a_{i + 1}$ for odd $i$ . Find a longest alternating subsequence.

Variant: Define a sequence $⟨ a_{0}, a_{1}, \dots, a_{n - 1} ⟩$ to be weakly alternating if no three consecutive terms are increasing or decreasing. Find a longest weakly alternating subsequence.

Variant: Define a sequence $⟨ a_{0}, a_{1}, \dots, a_{n - 1} ⟩$ to be convex if $a_{i} < \frac{a _{i - 1} + a _{i + 1}}{2}$ for $1 \leq i \leq n - 2$ . Find a longest convex subsequence.

Variant: Define a sequence $⟨ a_{0}, a_{1}, \dots, a_{n - 1} ⟩$ to be bitonic if there exists $k$ such that $a_{i} < a_{i + 1}$ for $0 \leq i < k$ and $a_{i} > a_{i + 1}$ for $k \leq i < n - 1$ . Find a longest bitonic subsequence.

Variant: Define a sequence of points in the plane to be ascending if each point is above and to the right of the previous point. How would you find a maximum ascending subset of a set of points in the plane?

Variant: Compute the longest nondecreasing subsequence in $O (n lo g n)$ time.

Answers

17.1

Let $co mbina t i o n s [i] [j]$ be the number of ways to make score $j$ using the first $i$ play types. Then each entry is the sum of the number of ways without using the current play and the number of ways using it at least once. Fill the table bottom-up. This gives $O (s n)$ time and $O (s n)$ space, reducible to $O (s)$ .

17.2

Define the edit distance between prefixes $A [0 : a - 1]$ and $B [0 : b - 1]$ . If the last characters match, the answer equals the distance on the shorter prefixes; otherwise it is $1 + min (substitute, insert, delete)$ . Caching or bottom-up DP gives $O (ab)$ time and $O (ab)$ space, with a standard rolling-row optimization to $O (min (a, b))$ space.

17.3

The number of ways to reach cell $(i, j)$ is the sum of the ways to reach $(i - 1, j)$ and $(i, j - 1)$ , with base case 1 at the origin and along the first row and first column. Fill a DP table or one rolling row/column. Obstacles simply zero out blocked cells.

17.4

Use Pascal’s identity: $(k n) = (k n - 1) + (k - 1 n - 1)$ with base cases $(0 x) = (x x) = 1$ . Since each subproblem value also fits when the final answer fits, memoization or bottom-up DP avoids overflow from factorial-style intermediate products. The complexity is $O (nk)$ .

17.5

Search for the pattern by recursively matching a suffix starting from a grid location. Cache failed states of the form $(x, y, o ff se t)$ so identical subproblems are not recomputed. This yields $O (nm ∣ S ∣)$ time for an $n \times m$ grid and pattern $S$ , rather than exploding exponentially.

17.6

For each prefix of items and capacity $w$ , store the best value attainable. The transition is $max (without current item, with current item)$ when the weight fits, otherwise just the former. This is the standard $O (n w)$ time, $O (n w)$ space DP, with a usual 1D rolling-array optimization to $O (w)$ space.

17.7

Let $l a s t_l e n g t h [i]$ record whether the prefix ending at $i$ can be decomposed, and if so the length of its final word. A prefix is valid if it is a dictionary word itself or if some earlier valid prefix is followed by a dictionary word. This supports reconstruction of one valid decomposition in polynomial time.

17.8

For each entry in row $i$ , the minimum path sum ending there depends only on the adjacent reachable entries in row $i - 1$ . Sweep row by row, updating each entry’s best achievable total. Reusing one previous row gives $O (n^{2})$ time and $O (n)$ space for a triangle with $n$ rows.

17.9

Let $R (a, b)$ be the maximum revenue the current player can guarantee from the subarray of coins indexed $a$ through $b$ . If the player takes the left or right end coin, the opponent then plays optimally to minimize the current player’s eventual total. This gives a min-max recurrence over intervals, solvable by interval DP in $O (n^{2})$ time.

17.10

Let $F (n, k)$ be the number of ways to reach step $n$ when jumps of 1 through $k$ are allowed. The last move could have been any size $i$ from 1 to $k$ , so $F (n, k) = \sum_{i = 1}^{k} F (n - i, k)$ with small base cases. Memoization or bottom-up DP yields $O (kn)$ time and $O (n)$ space.

17.11

Let $M (i)$ be the minimum messiness for laying out the first $i$ words. In an optimal layout, the last line contains some suffix of words ending at $i$ , and the preceding words must themselves be laid out optimally. Try every feasible starting point of the last line, compute that line’s messiness, and combine with $M (j - 1)$ . This gives $O (n L)$ time and $O (n)$ space when $L$ is the line length.

17.12

Let $L [i]$ be the length of the longest nondecreasing subsequence ending at index $i$ . Then $L [i] = 1 + max (L [j])$ over prior $j$ with $A [j] \leq A [i]$ , or 1 if none exist. Computing all $L [i]$ values gives the standard $O (n^{2})$ DP, and storing predecessor indices also lets you reconstruct an actual subsequence. The classic improved method uses patience-sorting style tails for $O (n lo g n)$ .

Takashi's Notes

Explorer

Dynamic Programming

Dynamic Programming

Problems

17.1

17.2

17.3

17.4

17.5

17.6

17.7

17.8

17.9

17.10

17.11

17.12

Answers

17.1

17.2

17.3

17.4

17.5

17.6

17.7

17.8

17.9

17.10

17.11

17.12

Graph View

Table of Contents

Backlinks