Back to all chapters
# Dynamic Programming

You don't want to repeat yourself when trying to be efficient. Dynamic programming is the art of keeping track of results you've already computed that are useful in later computations.

Consider the standard 2-egg problem. We wish to determine the critical height at which an egg breaks. That is we assume that there is some critical height \(C\), such that if we drop an egg from height \(h \leq C\) the egg does not break where as it will always break if dropped from height \(h > C\). We want to minimize the number of trials and we are only given two eggs.

Let us consider the worst case scenario. Let \(W(k)\) be the minimum number of trials required to identify \(C\) under the worst case scenario given that we have two eggs and a building a height \(k\).

How many values of \(k > 0\) satisfy \(W(k) = 18518505 \)?

Consider the classic egg drop problem. Let \(S(n,k)\) be the minimum number of egg droppings that will suffice to find the critical floor in an \(n\)-story building given \(k\) eggs.

\(S(k,n)\) can be described as follows for an elementary function of \(n\), \(f(n)\).

\[S(k,n) = \Theta(f(n,k)) \]

The function \(f(n,k)\) is given by which of the following?

×

Problem Loading...

Note Loading...

Set Loading...