Why is the essence of this world Dynamic Programming (DP)?

What is Dynamic Programming

DP in the coding world is usually the hardest type of problem when brushing up on algorithms, common in the last question of Leetcode weekly contests.

However, what exactly is DP?

It is an algorithmic idea.

The core part is to remember the optimal strategy calculated before.

aka, look-up table.

And this is actually the basic logic of world operation and human decision-making.

Optimal path planning is the most common DP problem.

There is also the most classic Fibonacci sequence.

KV Cache in the large model world is a classic DP idea.

All LRU Cache / Redis / CDN are the same idea.

There can be countless examples of computer science here, but more importantly, it is the inspiration in human life.

What are the DPs in reality?

When you are thinking, you are not starting from scratch, but from the last relevant memory. Our brain is not good at instant global calculation, but good at calling existing patterns that have appeared before. Just like “memoization” in dynamic programming: when you encounter a sub-problem, check if the solution has been stored first, and if so, reuse it directly.

Chess

When playing chess, memory rather than calculation at the opening, but already knowing how to play.

Your central cannon and jumping horse, your Queen’s Gambit, your golden corner, silver side and grass belly, are all DP tables summarized by humans in countless games.

When a professional chess player starts a game, he does not need to analyze every step from scratch. The basis for his move is often the opening routine practiced countless times in his memory. These memories may come from:

• Hundreds of actual combats;
• Formulas in books;
• Situations explained by the master;
• Vague visual images.

What his brain is doing is quickly matching the current situation with a path in the “memory bank” in his mind.

These steps are often the DP table synthesized by all human experience.

Masters can often memorize many steps of the chess manual.

Thinking often originates from “looking up tables”

Every time we think, we are actually mostly asking ourselves subconsciously:

Have I encountered a similar situation before?

Who have I heard tell a similar story?

Is there a familiar explanation that can be applied?

This is actually calling a “human version of the DP table” - a huge cache system continuously written and updated by our experience, education, and culture.

First Principles

Of course, there are exceptions.

First principles are to break the recent DP table and find a more stable starting point.

Memory is limited. Sometimes it gets outdated, biased, or simply not applicable.

At this time, what we need to do is to find a more primitive logical starting point.

This is like performing a cold start manually in a system full of caches: not relying on old results, forcibly re-solving once.

There will always be great people leading us to find more primitive logical starting points.

Like Newton, like Einstein.

Like Gauss.

Like Professor Hinton.

Standing on the shoulders of giants

So, this gives us an extremely profound inspiration:

Why do we study?

Not for exams, not to look smart - but to grab the DP table already written by others.

The process of learning a language

We didn’t understand grammar rules when we were young, but we would imitate and recite first. “Good morning”, “I love you”, “Have you eaten” - we didn’t understand the structure of these sentences at first, but directly called memory. Just like the pre-training stage of the language model, it is just a statistical pattern of violently piling up tokens.

But as the accumulation of memory tables reaches a certain level, suddenly:

Language “emerged”. You start to be able to form sentences, express, and jump out of example sentences to create new words.

This is not a flash of inspiration, but a natural result after the DP table is large enough and the state coverage is wide enough.

Inspiration

In this world, someone spent a lifetime walking through a complex and difficult path and recorded every step in the middle. And the meaning of our learning is to load these “intermediate results” into our own brain’s cache table, saving the cost of repeated trial and error.

• Reading books is extracting experience fragments settled by others;
• Reading biographies is copying the “state transition trajectory” of a whole life;
• Watching videos and listening to lectures is quickly absorbing other people’s observation angles and cognitive modes;
• And going to school is systematically loading the DP table collectively written by humans in a certain field.

The more accurately you can call these existing “memory tables”, the faster you can solve problems at critical moments, and even jump out of the routine to produce new solutions.

Even in a lifetime, you only need to call these DP tables to live a good life. Of course, you still want to live out your own wonderful life.

You are not a genius, but you can memorize the intermediate steps of many geniuses.

You are not a giant, but you can reuse the giant’s path.

You are not starting from 0, but starting from 99% of the existing answers to find the “last step” that belongs only to you.