Skip to content
Tutorials Center
My learning

Topics

Lesson 166 of 225 ยท Dynamic Programming

Egg Dropping, Rod Cutting and Classic DP Puzzles

Solve classic dynamic programming puzzles in Python: rod cutting, the egg dropping problem with a fast inverted state, domino tiling and counting binary trees.

Every field has a handful of textbook puzzles that everybody meets sooner or later, and dynamic programming is no exception. They are worth knowing by name: interviewers use them, and each one teaches a distinct way of choosing the state. In this lesson you will solve four of them: rod cutting, egg dropping, domino tiling and counting binary trees.

You should be comfortable with DP basics, memoization versus tabulation and the 1D recurrences from 1D dynamic programming. The knapsack-style reasoning in Knapsack is closely related to the first problem.

Rod cutting

You have a rod of length n and a price list: price[i] is what a piece of length i sells for. You may cut the rod into any number of integer pieces. What is the maximum total revenue?

Let best[len] be the best revenue for a rod of length len. The first piece you cut has some length i from 1 to len; the rest is a smaller instance of the same problem:

TEXT
best[len] = max over i in 1..len of ( price[i] + best[len - i] )
best[0]   = 0

This is an unbounded knapsack where the "weight" of an item is its length and the capacity is n. It runs in O(n^2) time and O(n) space.

Python Rod cutting with the cut list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Storing which first piece gave the maximum (first_cut) lets you rebuild the actual answer, a trick you can use in every DP in this lesson.

Egg dropping

You have e identical eggs and a building with k floors. There is an unknown critical floor f (0 to k): an egg dropped from floor f or lower survives, an egg dropped from above f breaks. A surviving egg can be reused; a broken egg cannot. What is the minimum number of drops, in the worst case, that guarantees finding f?

Think about one drop from floor x with e eggs and k floors left to examine:

  • If the egg breaks, f is below x: you now have e - 1 eggs and x - 1 floors.
  • If it survives, f is x or above: you still have e eggs and k - x floors.

The adversary picks the worse of the two, you pick the best x:

TEXT
drops(e, k) = 1 + min over x in 1..k of max( drops(e-1, x-1), drops(e, k-x) )
drops(e, 0) = 0,   drops(1, k) = k
flowchart TD
    S["e eggs, k floors<br/>drop from floor x"] --> B["egg breaks<br/>e - 1 eggs, x - 1 floors"]
    S --> N["egg survives<br/>e eggs, k - x floors"]
    B --> W["worst case = max of the two"]
    N --> W

One drop splits the problem in two; the answer is one drop plus the worse branch, minimized over x.

Python Egg dropping, the O(e k^2) recurrence

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This is O(e k^2) and too slow for big buildings. There is a much better way to see the problem: flip the question around.

The flipped state: how many floors can m drops cover?

Let floors(m, e) be the maximum number of floors you can fully resolve with m drops and e eggs. Drop from some floor: if the egg breaks you have m - 1 drops and e - 1 eggs to cover the floors below; if it survives you have m - 1 drops and e eggs for the floors above. Together with the floor you just tested:

TEXT
floors(m, e) = floors(m-1, e-1) + floors(m-1, e) + 1

You grow m until floors(m, e) >= k. The answer is that m. This runs in O(e x answer) time, and the answer is at most k, usually much smaller. It is the version you want in an interview.

Python Egg dropping with the flipped state

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With two eggs the coverage after m drops is 1 + 2 + ... + m = m(m + 1) / 2, which explains the famous strategy "drop from 14, then 27, then 39, ..." for 100 floors: the first drop starts at the floor that leaves exactly m - 1 steps for the linear search below it.

Domino tiling

How many ways can you tile a 2 x n strip with 1 x 2 dominoes (each placed vertically or horizontally)? Look at the leftmost column:

  • A vertical domino fills it, leaving a 2 x (n - 1) strip.
  • Two horizontal dominoes stacked fill the first two columns, leaving 2 x (n - 2).

So ways(n) = ways(n - 1) + ways(n - 2), the Fibonacci numbers again, with ways(0) = 1 and ways(1) = 1.

A harder variant allows 2x1 dominoes and L-shaped trominoes, which needs a second helper array for "one cell sticking out". The way to find those relations is always the same: look at how the boundary can be filled and name every partial shape you can leave behind.

Python Tiling a 2 x n strip

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting binary search trees

How many structurally different binary search trees can you build from the keys 1..n? Pick any key r as the root. The r - 1 smaller keys form the left subtree and the n - r larger keys form the right subtree, independently:

TEXT
trees(n) = sum over r in 1..n of trees(r - 1) * trees(n - r),    trees(0) = 1

These are the Catalan numbers (1, 1, 2, 5, 14, 42, ...). The same recurrence counts balanced parentheses strings, ways to triangulate a polygon and many other things, so recognising the shape pays off. See combinatorics for the closed form C(2n, n) / (n + 1) and binary search trees for the structure being counted.

Python Catalan numbers by DP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The DP is O(n^2); the closed form is O(n). Both are fine here, but the DP generalises to problems with no formula, such as counting trees under extra constraints.

What these puzzles teach

  • Rod cutting: the state is the remaining length; the transition tries every first piece (an unbounded knapsack).
  • Egg dropping: when the obvious state (floors) is too slow, swap the roles of answer and state (drops become the index, floors the value). This "invert the DP" idea also solves some binary-search-on-answer problems.
  • Tiling: the state is the shape of the boundary; try the leftmost free cell.
  • Catalan: split on the root or on the first or last element, then multiply independent halves.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In rod cutting, what does best[len] = max(price[i] + best[len - i]) choose?

    We try every possible first piece length i and add the best revenue of what remains, then keep the maximum.
  2. 2. With 1 egg and 10 floors, how many drops do you need in the worst case?

    With one egg you cannot risk a break, so you must test floors from the bottom upward. The worst case is 10 drops.
  3. 3. What is the recurrence of the flipped egg-drop state?

    One drop tests a floor, covers the floors below with m-1 drops and e-1 eggs (if it breaks) and the floors above with m-1 drops and e eggs (if it survives).
  4. 4. Which sequence counts the structurally different BSTs on n keys?

    Choosing a root splits the keys into independent left and right parts, giving trees(n) = sum of trees(r-1) * trees(n-r), the Catalan recurrence.

Summary

  • Rod cutting is an unbounded knapsack: best[len] = max(price[i] + best[len - i]), O(n^2); remember the first cut to rebuild the pieces.
  • Egg dropping: the plain recurrence is O(e k^2); inverting the state to "floors covered by m drops" gives floors(m, e) = floors(m-1, e-1) + floors(m-1, e) + 1 and a fast solution.
  • Tiling a 2 x n strip with dominoes follows Fibonacci; model the boundary shape to handle harder tilings.
  • Counting BSTs gives the Catalan numbers by splitting at the root.
  • When a DP is too slow, try changing what is the state and what is the value.

Next: Greedy Algorithms, where we stop exploring all choices and commit to the best local one.