Algorithms and Data Structures for Programming Contests

Dynamic Programming (Cont'd)

Regroup (1)

High-level solution?

Is it recursive?

Yes: solution either does not use last block (fewer blocks, same target height) or it uses last block (fewer blocks, reduced target height).

Does it have optimal substructure?

Yes: if optimal solution does not use last block, then it is optimal for rest of blocks;
if optimal solution uses last block, then it is optimal for rest of blocks and reduced height.

Are subproblems "simple"?

Yes: each subproblem characterized by target height (range [0..H]) and index of last block available (range [0..S]).

Do subproblems overlap?

Yes: small subproblems (e.g., with S = 1) must be evaluated multiple times as part of solving larger problems.

Step 1: define a table of solutions.

• In general, table indexed by subproblem.
  In this case, use indices h ∈ [0..H] and s ∈ [0..S] (so table is 2D-array with H+1 rows and S+1 columns).
• In general, array values = quantity to optimize.
  In this case, table[h,s] = minimum number of blocks that stack to exactly h, using only blocks 1..s — 
  table[h,s] = 0 if h cannot be reached exactly using only blocks 1..s.

Step 2: write recursive equations for table values.

• This step is the most important — and difficult!
• Start with base cases — values that can be computed directly.
  In this case,
  • table[0,s] = 0 for s = 0,...,S — no block required to reach height 0;
  • table[h,0] = S+1 for h = 1,...,H — height h unreachable without any block.
• Next, write a "recurrence" (i.e., recursive equation) for the general case.
  In this case, for h = 1,...,H and s = 1,...,S:
  • let b_s = height(block s);
  • if b_s > h, let table[h,s] = table[h,s−1] — block s cannot be used;
  • else, table[h,s] = min(table[h,s−1], table[h−b_s,s−1] + 1) — either don't use block s, or use it and do the best possible with the remaining blocks.

Step 3: write the algorithm.

• This is comparatively simple: use nested loops to compute the table values according to the recursive equations from the previous step.
• Make sure that entries are filled in so that by the time an entry is computed, the other entries it depends on have already been filled in.
  In this case, simply use an outer loop over s with an inner loop over h.

Step 4: reconstruct the solution.

• By the time the algorithm is done, what information do we have?
  The entry table[H,S] tells us the smallest number of blocks that stack up to height H (or is greater than S if this is not possible).
• This is exactly the answer required for the problem! But in general, we may want to know what blocks to use to actually reach height H.
• This information is not stored anywhere directly. But it can easily be reconstructed, because of the way the entries in the table are computed:
  • if table[H,S] = table[H,S−1], then block S was not used;
  • else, block S was used.
• So the solution can be reconstructed with a simple loop like this:

      blocks = []
      h = H
      for s = S,S-1,...,1:
          if table[h,s] != table[h,s-1]:
              blocks.append(s)
              h = h - height of block s
  

Try it! (2)

• Try the "Playlist" problem from the DWITE programming contest.
• Ignore issues of input/output for now: suppose you already have the data stored in an appropriate data structure of your choice.

Regroup

© Copyright 2012–2015 François Pitt <francois.pitt@utoronto.ca>
last updated at 08:24 (EST) on Thu 5 Mar 2015
Algorithms and Data Structures by François Pitt is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.