This chapter introduces dynamic programming (Dynamic Programming, DP), the problems it solves, and the algorithms and optimizations designed around it.
Dynamic programming is a method for solving complex problems by decomposing the original problem into relatively simple subproblems.
Since dynamic programming is not a specific algorithm but a method for solving particular problems, it appears in all kinds of data structures, and the types of related problems are also more varied.
In OI, recursive solutions to non-optimization problems such as counting are also often nonstandardly called DP, so this chapter lists them together. In fact, dynamic programming and other types of recursion do have many similarities; while learning, you can pay attention to their similarities and differences.