×
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.

# Dynamic Programming: Level 3 Challenges

You are given access to a 100-storey building and an infinite number of eggs. The eggs are identical.

The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

Adopting the best strategy, what is the absolute minimum number of egg drops that you need to reach the solution given any scenario (Including worst case)?

Details and Assumptions: - Issues related to terminal velocity, potential energy or wind resistance are immaterial.

###### You can solve Super Strong Eggs --- II here.

What is the minimum number of characters than need to be inserted to to the string Brilliantforever to make it a palindrome?

As an explicit example:

-"ba" becomes a palindrome by adding 1 character as bab

-"lov" becomes a palindrome by adding 2 characters as lovol

Details and Assumptions

Characters can be inserted at any postion

How many checkers can you place on a 8-by-8 checkerboard without any checker having three (or more) neighbors?

"Neighbor" refers to a checker that is adjacent horizontally or vertically only.

###### Image credit: Imperial War Museums

This problem was inspired by this problem.

After having his demon henchmen thwarted by the cunning mathematician village chiefs of Earth,the devil himself comes down to Earth to get rid of the problem once and for all.

Confidently he snarls

" All you people of Earth stand in a large CIRCLE and number yourself starting from $$1$$ to $$10^7$$. I will devour every $$666th$$ person and keep going around and around the circle eating up every $$666th$$ person and keep doing this till there is only $$1$$ person left. That last person I will spare and he is free to escape. "

You are the last living descendant of the mathematician village chiefs and need to ensure that you survive so that mathematics will not perish from Earth.

Which number will you choose to be the last person standing and escape the clutches of Satan?

Details and assumptions

• Assume all this happened a long time ago and that Earth only had $$10^7$$ inhabitants.
• Satan will start eating from the $$666$$th person.
• This is an instance of a very famous problem called the Josephus Problem.

Example

• It there were $$9$$ people and every $$5$$th person was eaten the people eaten would be $$5\rightarrow 1\rightarrow 7\rightarrow 4\rightarrow 3\rightarrow 6\rightarrow 9\rightarrow 2$$ leaving the $$8$$th person alive.

You are given just two eggs, and access to a 100-storey building. Both eggs are identical.

The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

Adopting best strategy what is the absolute minimum number of egg drops you need to reach the solution given any and every possible scenario?

Details and Assumptions:

• Issues related to terminal velocity, potential energy or wind resistance are immaterial.
×