Dynamic programming of php algorithm learning

Dynamic programming programming is a way and a method to solve optimization problems. The optimal solution of the final problem can be derived from the optimal solution of the previous sub-problems.

Regarding the dynamic programming algorithm, I have not learned it thoroughly. A simple summary of my learning experience is:

Dynamic programming ideas incorporate the ideas of recursion and divide and conquer. , but different from divide and conquer, in dynamic programming solving, the optimal solution of each branch in the solving process will be recorded through the state, thus saving repeated calculations of many branches.

The most important and difficult two steps of dynamic programming are to find the state that describes the sub-problem and the derivation relationship between states.

Problems that are more likely to use dynamic programming: finding the maximum and minimum values, whether there are feasible solutions and the number of feasible solutions.

Let’s try the most common question first, find the value of a certain position in the Fibonacci sequence (students who don’t know, please search it on Baidu)?
Applying the divide-and-conquer method to solve the code

During the divide-and-conquer solution process, there will be many repeated operations. Figures 3 and 2 below are both repeated twice. The larger the index value, the more times it is repeated.

#ok, let’s take a look at how dynamic programming can be optimized.

We define an array to record the value of each position of Fibonacci, which is equivalent to us defining a state; the value of each position It is equal to the sum of its previous two, which is equivalent to a state transition equation.
Recording status through an array here is an idea of ​​exchanging space for time. In fact, it is very similar to the cache design we use in daily development.

Summary Dynamic programming solution can be divided into 4 steps:
1. Determine the sub-problem to be solved, that is, the definition of the state.
2. List the state transition equation.
3. Initialize the known state value according to the given conditions.
4. Solve the final problem solution.

Let’s solve a more interesting problem, climbing stairs:

The above is the content of dynamic programming of PHP algorithm learning, please pay attention to more related content PHP Chinese website (www.php.cn)!