We'll break down why these intimidating "fancy names" are used to label & further confuse a lot of us when trying to learn straightforward & logical terms in programming.
I will give you an easy real-world analogy to explain what Dynamic Programming is all about.
Plus points to you if you love ‘How I met your mother’!
Imagine,
I am your boss.
You work for me.
I am not nice.
I want the results.
You are going to do everything to please me.
So, as your first task of the month,
I ask you to do “critical” things.
Me:
“ Hey, you have to watch Season 3 & Season 4 of ‘How I met your Mother’.
Alright, I can have that done by the end of today.”
Now here’s the real question.
Did you say “by today”?
Why so much faster this time?
Only “one day” instead of “two days”?
The answer is obvious.
You already did Season 4 from your last task, part 1 of the new task.
Now, you can focus on doing part 2 of the new task.
In real life,
It’s called using your “common sense.”
Not “Dynamic Problem-Solving.”
Of course, you would exaggerate simple terms heavily on your resume.
Your teacher?
Eh, they want to sound smart + cool.
Don’t we all? 🤔
Basically, in programming,
We love to give an “impressive” sounding name.
A long scientific Wikipedia definition of Dynamic Programming rings the same bell.
Richard E. Bellman actually just wanted to sound cool.
Scientifically, they use “fancy Greek notations” to really seal the deal.
The word “Dynamic” was chosen to capture the time-varying aspect of the problem.
Because it sounded:
What is Dynamic Programming?
In simple terms,
Breaking down “problems.”
Into “sub-problems.”
Which in turn breaks into
Their own “sub-problems.”
By solving those “sub-problems” & “remembering” the answers,
So that you don’t have to solve the same problems multiple times.
You savetime.
That’s about it.
A couple of pre-requisite for it to qualify as Dynamic Programming.
Optimal Substructure
Overlapping Sub-Problems
Optimal Substructure
The optimal solution to the problem has to be some combination of the optimal solution of its sub-problem.
If you solve the sub-problems in the best way possible,
You solve the main problem.
Overlapping Sub-Problem
When you are solving the problem,
You are doing a lot of redundant work solving the same problems over & over again.
Of course, those sub-problems that are getting redone,
They have to be deterministic.
Otherwise, you can’t save the results.
There are two ways to tackle a Dynamic Programming problem.
Memoization
Tabulation
Memoization
Not “memorization”
Recursive solution (Top-Down approach)
Just an optimization where you don’t just compute the same thing over & over again.
It’s “caching” the returned results of somefunctions.
If you happen to call that functionagain, with the same parameter,
Surprise!
You just returned the cached result instead.
A rough example I put together in JavaScript:
function ComputeSlow(randomthings) {
// Ok now do some shit
return randomthings * 2;
}
const CACHED_RESULTS = {};
function Memoized_ComputeSlow(randomthings) {
if (randomthings in CACHED_RESULTS) {
return CACHED_RESULTS[randomthings];
}
const result = ComputeSlow(randomthings);
CACHED_RESULTS[stuff] = result;
return result;
}
Before you jump into questions, look at them carefully.
Tabulation
Iterative (Bottom-Up approach)
Generally, the same idea as memoization.
Working towards the solution by building up from smaller solutions.
Typically, by filling out a table (tabulation).
For example, an Array. They are filling ahead of time.
