9

7

Here is the Problem Description :

Suppose that we wish to know which stories in a N-story building are safe to drop eggs from, and which will cause the eggs to break on landing. We make a few assumptions: An egg that survives a fall can be used again.

- A broken egg must be discarded.
- The effect of a fall is the same for all eggs.
- If an egg breaks when dropped, then it would break if dropped from a higher window.
- If an egg survives a fall then it would survive a shorter fall.
- It is not ruled out that the first-floor windows break eggs, nor is it ruled out that the Nth-floor windows do not cause an egg to break.

Given an N story building and a supply of d eggs, ﬁnd the strategy which minimizes (in the worst case) the number of experimental drops required to determine the breakﬂoor.

I have seen and solved this problem for 2 eggs where answer comes out to be 14 for N=100. I tried to understand the generalized solution from wiki using DP but couldn't Understand what are they trying to do. Please tell how they arrived at the DP and how it is working ?

**EDIT :**

The Recurrence given in this Article for the The highest ﬂoor that can be tested with d drops and e eggs is as follows :

```
f[d,e] = f[d-1,e] + f[d-1,e-1] + 1
```

The recurrence is fine but i not able to understand how it is derived ?

The explanation is not clear to me....i just want someone to explain this recurrence to me in more clear words.

Are you missing some context? Who are "they" and what is the wiki you're talking about? – Weeble – 2012-04-16T20:09:54.920

Without looking at the document you linked, that recursive expression looks strikingly similar to the way combinations can be calculated. – biziclop – 2012-04-16T20:14:51.317

Wiki was the Explanation for the Puzzle on the wikipedia page http://en.wikipedia.org/wiki/Dynamic_programming#Egg_dropping_puzzle and "they" were used as the general for the resources on the net for this particular problem.

– Amol Sharma – 2012-04-17T02:30:20.223