Detailed introduction to dynamic programming (with examples)

Dynamic Programming：

Definition ：

DP Definition ：
Dynamic programming is an extension of the idea of partition , Generally speaking, it means making big things small , The art of trivialization .
In the process of dividing big problems into small ones , Save the results of these small problems , And these results can be used directly when dealing with larger problems later .

characteristic ：

Dynamic programming has the following three characteristics

1. The original problem is decomposed into several similar subproblems .
2. All subproblems need to be solved only once .
3. Store the solution of the subproblem

The essence ：

It is the definition of the problem state and the state transfer equation ( States and the recursive relationship between States )

Consideration angle ：

Dynamic programming is generally considered from the following four perspectives ：

1. State definition
2. The transfer equation between States is defined
3. Initialization of state
4. Return results

Requirements for state definition ：

The defined state must form a recursive relationship

One sentence summary :

Three characteristics, four elements and two essences

Applicable scenario ：

Maximum / minimum value , Not feasible , Is it right? , Number of schemes

Topic explanation ：

The first question is ： Fibonacci sequence

https://blog.csdn.net/sakeww/article/details/122770286

The second question is ： String segmentation (Word Break)

https://blog.csdn.net/sakeww/article/details/122857096

Third question ： Trigonometric matrix (Triangle)

https://blog.csdn.net/sakeww/article/details/122861135

Fourth question ： The total number of paths (Unique Paths)

https://blog.csdn.net/sakeww/article/details/122863621

Fifth question ： Minimum path sum (Minimum Path Sum)

https://blog.csdn.net/sakeww/article/details/122864886

Sixth question ： knapsack problem

https://blog.csdn.net/sakeww/article/details/122867718

Question seven Palindrome segmentation (Palindrome Partitioning)

https://blog.csdn.net/sakeww/article/details/122894050

The eighth question Edit distance (Edit Distance)

https://blog.csdn.net/sakeww/article/details/122899542

Question 9 Different subsequences (Distinct Subsequences)

https://blog.csdn.net/sakeww/article/details/122900255