Decompose a large problem that is difficult to solve into several smaller sub-problems, divide and conquer them, and then merge them to obtain the solution to the original problem

① Can be decomposed into several smaller-scale identical problems

② Reducing the scale to a certain extent can make it easier to solve

③The solutions to each sub-problem can be combined into the solution to the original problem

④Each sub-problem is independent of each other

Decomposition: Decompose the original problem into several smaller, independent sub-problems with the same form as the original problem.

Solution: If the sub-problem is small and easy to solve, solve it directly, otherwise solve each sub-problem recursively.

Merge: merge the solutions of each sub-problem into the solution of the original problem

binary search

Quick sort

merge sort

chessboard overlay

Tower of Hanoi

Divide the original problem into sub-problems in several stages, solve the local optimal solution of each stage in order, and provide relevant information for the next stage. When the optimal solution of the final stage is found, it is the solution of the original problem.

①Satisfies the optimization principle: If the optimal solution of a problem contains solutions to sub-problems that are also optimal, the problem is said to have optimal substructure, that is, it satisfies the optimization principle.

②No aftereffect: subsequent decisions will not affect the previous state

③ There are overlapping sub-problems: The sub-problems are not independent, and a sub-problem may be used multiple times in subsequent decisions.

Divide the stages:

Determine the state and state variables:

Determine the decision and write the state transition equation:

Find boundary conditions:

Three elements

Fibonacci sequence

0/1Backpack Problem

That is, the depth-first strategy. Go down a road. If this road is blocked, go back to the previous fork and choose another road to continue walking until all paths are traversed.

depth first search

Binary tree preorder traversal

Eight Queens Problem

maze problem

That is the breadth first strategy. Layer-wise expansion checks all nodes until the final result is found.

breadth first search

Dijkstra finds the shortest path

prim algorithm

When solving problems, always make the best choice at the moment. There is no guarantee of global optimality, but it may be better.

no aftereffects

The best local optimal strategy can lead to the global optimal solution

Dijkstra finds the shortest path

prim algorithm

Kruskal algorithm

traveling salesman problem