Somewhere along historic Route 66 (probably in Texas), you'll find The Big Texan. Despite the name, it isn't a person, it's a restaurant. The biggest thing on the menu is a 72 oz. steak, which you can get for free. All you have to do is eat all of it yourself.

In an hour.

Without leaving the table.

Yeah…good luck with that one.

That isn't a small problem, and it's not a problem you can solve all at once. Mouths just aren't big enough to handle that much steak. You have to break it down into a bunch of manageable sub-problems, the kind you can fit in your mouth.

You have to do the same thing for big computer science problems, except you can take bathroom breaks if you need to. You'll also probably have more success with our problems than with that giant steak. (Sure, you don't have to fork over any cash if you eat it all, but you'll pay for it in other, gastro-intestinal ways.)

Let's take a shot at breaking down a less gluttonous problem into sub-problems with that optimal substructure (those are the sub-problems that have a clear best solution, by the way).

Here's the problem: find Fibonacci(n), when n = 5. The Fibonacci sequence is a series of numbers where you can find the next number by adding the two numbers before it. That means:

• The fifth Fibonacci number equals the fourth Fibonacci number plus the third
• The fourth Fibonacci number equals the third Fibonacci number plus the second
• The third Fibonacci number equals the second Fibonacci number plus the first 
• The second Fibonacci number equals the first Fibonacci number plus the zeroth

There. We just broke the problem down. At every single entry, there's one, optimal solution. If you can't find one optimal solution to a problem, then you can't be sure that breaking the problem down will give the optimal solution.

You can also build up from Fibonacci(5) (imagine that), making Fibonacci(5) the sub-problem to a bigger problem. As you break down the solution for that problem with a larger n, you'll eventually get down to Fibonacci(5). Then, everything beneath Fibonacci(5) down would look exactly the same as calling Fibonacci(5) itself.

That kind of logic tells you that the solution for Fibonacci(n) for any value of n can be solved with optimal sub-structure.

And we aren't even fibbing to prove it.

(…Sorry, we had to do that one.)