constant space

linear space

Two-dimensional space

recursive space

Similar to change in daily life, each time the banknote with the largest denomination is selected, and the total amount of the banknotes that have been selected does not exceed the amount payable, the banknotes are given to the other party. This method is called a greedy algorithm.

The problem has at least one optimal solution. Only in this way is it possible to construct a set of candidate solutions for solving the problem.

As the problem is solved, two other sets will be established. One set (assumed to be set a) is composed of candidate solutions that have been selected and meet the requirements of the problem. The other set (assumed to be set b) is composed of candidate solutions that have been selected. But it is composed of candidate solutions that do not meet the requirements of the problem.

Set a ultimately contains the solution to the problem. When no solution appears in set a, at least one candidate solution remains in the set of candidate solutions to the problem.

Minimum spanning tree problem for graphs (Kruskal's algorithm and Prim's algorithm)

Shortest path problem for graphs (Dijkstra's algorithm)

The problem of average time for minimum task execution

backpack problem

When calculating multiplication, instead of multiplying two numbers directly, one of the multipliers is "decomposed". This decomposition and solution method is called the divide and conquer method.

Divide the problem into sub-problems one by one, and solve the original problem by solving the sub-problems.

The entire problem can be decomposed into two or more smaller sub-problems

Solving each subproblem is similar to solving the entire problem

If the size of the sub-problem is still quite large and it is inconvenient to solve the sub-problem, then use the divide-and-conquer method to solve the sub-problem.

infectious disease issues

Binary search and quick sort

Matrix multiplication

Tower of Hanoi problem

Avoid solving the same problem twice

Algorithms need to solve a lot of repetitive work and calculate a lot of repetitive data.

At least some new values ​​can be combined from already calculated values

The problem must be of a certain scale so that the benefits of dynamic programming algorithms can be highlighted

When using the divide-and-conquer method to divide sub-problems, the relationships between sub-problems are unclear and intersect with each other. The solution of a subproblem is related to multiple solved subproblems

Fast Fourier problem

Optimal segmentation of polygons

Change problem

shortest path problem

backpack problem

Chained matrix multiplication

The problem can be divided into several unrelated sub-problems

Several subproblems have similar solutions

If the subproblem can still be divided, the edge continues to divide the subproblem.

maze problem

Eight Queens Problem

Knight travel problem

Depth first traversal of graph

are algorithms that produce different results for the same input

Buffon's Needle Problem

Verify matrix multiplication

prime number test

Factoring large integers