# The Ultimate Summary of Dynamic Programming!

Now that 42 classic problems on dynamic programming with a total of 50 articles have been discussed, it is time to make a summary.

Regarding dynamic programming, in the first article of the topic Dynamic Programming Fundamentals (opens new window), the five steps of dynamic programming were introduced and emphasized as crucial for solving dynamic programming problems!

These are the distilled pearls of wisdom Carl has gathered from completing over one hundred dynamic programming problems. If you've followed along with the "Coding Thoughts" series on dynamic programming, you'll deeply appreciate the significance of these five steps.

The five steps of dynamic programming are:

Define the dp array (dp table) and the meaning of its indices.
Determine the transition formula.
Initialize the dp array.
Decide on the order of traversal.
Deduce the dp array through examples.

At the start of the dynamic programming section, the problems discussed were relatively simple. Many readers mentioned that these simple problems seemed to be over-explained and could be solved directly by figuring out the transition formula.

Carl's perspective has always been that simple problems are meant to reinforce methodology. Simple problems can be tackled by intuition, but slightly more difficult problems are likely to defy such an approach.

Throughout the dynamic programming discussion, the importance of these five steps has consistently been highlighted.

Some readers believe that discovering the transition formula is the most challenging and crucial step, and once it's found, the rest follows easily.

However, if you think this way, your understanding of dynamic programming is likely incomplete.

In dynamic programming, if any of these steps are unclear, the problem can hardly be solved; even if it is, it hasn't been thoroughly understood, and the process feels foggy at best.

If the specific meaning of the dp array is unclear, how can you discuss a transition formula? You may even make mistakes during initialization.
For example, in 0063.Unique Paths II (opens new window), initialization is the key focus.
If you've reviewed the knapsack series, especially the complete knapsack, the ordering of the two for loops can certainly confuse many people, while the transition formula is straightforward.
As for the importance of deducing the dp array, it's almost always emphasized in each article within the dynamic programming section: when the program's output is incorrect, you must deduce the formula yourself to check it against the program's logs.

Great, let's revisit the content we've covered in the dynamic programming section.

# Basics of Dynamic Programming

# Knapsack Problem Series

Knapsack Problem Outline

# House Robbery Series

# Stock Series

Stock Problem Summary

# Subsequence Series

# Concluding Remarks on Dynamic Programming

Beyond dynamic programming, there are other types such as Tree DP (with one problem shown in the House Robbery series), Digit DP, Interval DP, Probability DP, Game DP, State Compression DP, etc. I won’t be explaining these; their occurrence in interviews is quite low.

If you thoroughly research all the problems listed in this article, your level of understanding of dynamic programming will be very high. It will be more than sufficient for interviews!

This diagram is created by a member Qing (opens new window) from the Coding Thoughts Knowledge Community (opens new window). It’s beautifully summarized and I'd like to share it with everyone.

This should be the most detailed explanation series on dynamic programming available online.

In fact, if you search online, you'll find that there are very few resources that can explain dynamic programming clearly because it is indeed challenging! Explaining it to others is even harder!

In "Sword Offer Background," dynamic programming problems are scarce; the classic algorithm book "Algorithm 4" does not discuss dynamic programming, and "Introduction to Algorithms" covers it at a level that could be quite discouraging.

Explaining a single problem clearly is easy, explaining two problems clearly is easy, but thoroughly elucidating dynamic programming in its entirety and implementing it with a consistent methodology throughout is extremely difficult.

Therefore, Carl has devoted significant efforts to sharing his complete understanding of dynamic programming to help you avoid detours. Keep going!

← 46. Longest Palindromic Subsequence 1. Daily Temperatures →