Oh, The Problems You’ll Solve!
Consider, oh won’t you, a practical quest -
how to make something great without having to guess.
That’s optimization; it’s really a blast.
The problem, it seems, lies in doing it fast.
If, for example, you’re given two strings
and must locate the largest collection of things
that the strings have in common, subject to some rules,
oh wouldn’t that be such a marvelous tool?
The quick way to find such collections, of course
is to roll up your sleeves and to just use brute force.
“It will take a while, ” you chortle with glee,
“but you will all just have to wait up for me!
My program will find them, will search near and far,
and then it will tell what the longest ones are!”
If your strings are quite small, this might work fairly well
there aren’t many collections, it’s easy to tell.
But be warned, simple noob, it is not wise to kludge
if the strings that you search are sufficiently huge
You’ll wait,
and you’ll wait,
and you’ll wait wait wait wait
’til your cup full of coffee begins to stagnate.
For the time to compute grows in time exponential
to the size of what’s given, and that’s consequential!
You don’t want to wait ’til your processor’s fried
and your hard drives have head-crashed and you have, well, died.
The answer, of course, lies in hours of thought.
What parts of my program are running a lot?
There must be a way to remember what’s done
and to not do it twice … that will save me a ton!
Furthermore, if you’re already saving some space,
there’s no reason why this can’t be done all in place.
Solve all the subproblems, from bottom to top,
when you get to the right one, report it and stop!
The improvement, you’ll find, is really dramatic
What was once exponential becomes now quadratic
Oh the problems you’ll solve! What a haxor you’ll be!
if you solve wicked problems by using DP.