Core of Dynamic Programming: Definition of State and Definition of State Transition Equation
As for other common topics like overlapping subproblems, no aftereffect, and optimal substructure, they all revolve around these two core contents.
In the state transition equation mentioned above, the values with subscripts greater than the left side or will not be used on the right side of the equation. This is the colloquial mathematical definition of "no aftereffect." States that meet this definition can be said to possess the property of "optimal substructure." What we need to do in dynamic programming is to find such "optimal substructure."
In the process of defining states and state transition equations, satisfying "optimal substructure" is an implicit condition (otherwise, it cannot be defined at all).
It is important to note that a problem may have multiple different definitions of states and state transition equations. The existence of a definition with aftereffect does not mean that the problem is not suitable for dynamic programming. This is also a logical misconception that appears in several other answers: the dynamic programming method seeks to find definitions of states and state transition equations that conform to "optimal substructure." Once found, the problem can be solved using the method of "memoized recursive formulas." The definitions found are the essence of dynamic programming.
Each stage has only one state -> recursion;
The optimal state of each stage is derived from the optimal state of the previous stage -> greedy;
The optimal state of each stage is obtained from the combination of states from all previous stages -> search;
The optimal state of each stage can be directly obtained from a certain state or states of a previous stage, regardless of how that state was obtained -> dynamic programming.
The property that the optimal state of each stage can be directly obtained from a certain state or states of a previous stage is called optimal substructure;
and the property that it does not matter how that state was obtained is called no aftereffect.
Note: In fact, the term "optimal state" in dynamic programming can be misleading, leading one to think that it is sufficient to calculate only the optimal state. This is indeed the case for the LIS problem, where only the states "chosen" at each stage are used during transitions. However, in reality, some problems often require calculating an optimal value for all states at each stage and then finding the optimal state based on these optimal values. For example, the knapsack problem requires calculating the maximum value when considering the first items (stages) with a capacity of (state). Then, the optimal value is found among all states in the last stage.