You are given an unlimited supply of tiles. Each tile has one letter on it and has a point value. If the letter is A, the point value is 1. If the letter is B, the point value is 2. If the letter is C, the point value is 3. If the letter is D, the point value is 1. Each word that can be constructed from these tiles has a values obtained by adding the values of the tiles. For example, the word AABCAD has value 9. There are exactly 5 words whose point value is 2, namely AA, AD, B, DA, DD. Design an O(n)-time dynamic programming algorithm that computes, for a given integer n, how many words with point value $n$ can be constructed from these tiles.
You are given a weighted directed acyclic graph G, a start node s in G. You are also given a positive integer k.
The problem is to find k directed paths starting at s, such that every node of G lies on at least one of those paths.
Define N(i) to be the number of words of total value i that can be constructed from those tiles. The linear time dynamic program algorithm computes the values of N and stores them in an array.
The initial values are
N(-2)=0 because there is no word which has negative total value.
N(-1)=0 also because there is no word which has negative total value.
N(0)=1 because there is one word of toal value zero, namely the empty word. (Did you think of that?)
Now, the recursive part of the definition of N, which corresponds to the body of the main loop of the dynamic program.
For i > 0, we have that N(i) = 2N(i-1) + N(i-2) + N(i-3) The explanation is this: if a string of tiles has total value i, then it must have a last tile. That last tile is A, B, C, or D. If we remove that last tile, the remaining tiles form a string of total value i-1 if the tile removed was either A or D, a string of total value i-2 if the tile removed was B, and total value i-3 if the tile removed was C. The number of ways this can be done is thus the sum of the numbers of ways of each of those four cases, and those values are already known.
The value of N(n) is the answer.
You might question the necessity of storing values for negative i. The reason is that, for i = 1, we have that i-2 and i-3> are both negative.
Back to Course Page
Back to Assignments Page