There are three general ideas for solving dynamic programming problems, the backtracking algorithm, and the other two algorithms are the state transition table method and the state transition equation method. At algo.monster, we separate these three methods and talk about the backtracking algorithm first before emphasizing the other two algorithms.
Backtracking method in dynamic programming
The backtracking algorithm can solve any problem that can be solved by dynamic programming.
What is the backtracking method?
The backtracking method (exploration and backtracking method) is a selective search method, also known as the trial method, which searches forward according to the demanding conditions to reach the goal. However, when the exploration comes to a certain step, it is found that the original choice is not superior or does not reach the goal, so it backtracks to a new option.
Vernacular: we can see backtracking as finding the destination by choosing different forks, one fork at a time, to find the goal. If you go the wrong way, keep going back to see the other way at the fork until you find the destination.
Backtracking method to solve dynamic programming problems
When you get the problem, you can first use a simple backtracking algorithm to solve it. Define the states. Each state represents a node and then draws the recursive tree correspondingly. From the recursive tree, it is easy to observe whether there is a duplicate subproblem and how to generate it. It is to find the pattern and see if dynamic programming can solve it.
After finding the duplicate subproblem, there are two ways to deal with it. The first one is to use the method of backtracking and “memoization” to avoid duplicate subproblems. In terms of execution efficiency, this is no different from the dynamic programming approach.
State transition table method in dynamic programming
The second type of solution is the dynamic programming method, the state transition table method.
What is the state transition table method?
A state transition table is a state transition diagram in the form of a table. And the two are essentially the same. There are two forms of state transition table. One is to use the present state and sub-state to express the state change before and after the arrival of the clock pulse. This method does not require a separate list of clock pulses; the other is to list each state in turn according to the order of time. This method requires the left side of the state transition table listed in the order of change of the clock pulse CP.
How to solution
For this idea, draw a state table first. The state table is generally two-dimensional. And it can be imagined as a two-dimensional array where each state contains three variables, rows, columns, and array values.
Then, each state in the state table is populated in stages according to the sequential process of decision making, from front to back, based on recursive relationships.
Finally, write this recursive process of filling the table into code, which is the dynamic programming code.
Use the state transition table method in dynamic programming
However, if the state of the problem is complex and requires many variables to represent, then the corresponding state table may be high-dimensional instead of two-dimensional. In this case, using the state transition table method to solve is not the best way. On the one hand, the high-dimensional state transition able is not good at drawing diagrams. On the other hand, the human brain is naughty at thinking about high-dimensional things.
Now try to use the state transition table method to solve the problem of the shortest path of the rectangle before. There are many different ways to go from the start to the end. We can exhaust all the methods and then compare them to find the shortest route to go. For this process, we can use the backtracking algorithm, which is a more standard exhaustive algorithm, to exhaust all the walks without duplication and without missing.
Next, draw a recursive tree to find duplicate subproblems. In a recursive tree, a state (i.e., a node) contains three variables (i, j, dist), where i and j denote rows and columns, respectively, and dist denotes the length of the path from the starting point to (i, j). In the following figure, we can see that although there are no duplicates of (i, j, dist), there are many duplicates of (i, j). For the nodes with replication (i, j), we only need to select the node with the smallest dist and continue the recursive solution. And the other nodes can be discarded.
Since there is a duplicate subproblem, can we use dynamic programming to solve this problem?
First, draw a two-dimensional state table, where the rows and columns in the table represent the positions of the pieces. And the values in the table represent the shortest path from the starting point to this position. According to the decision process, fill the state table with a continuous state recursive evolution.
State transition equation method in dynamic programming
The third method is the state transition equation method.
What is the state transition equation method?
The state t transition equation is dynamic programming in which the state of the current stage is often the result of the state of the previous step and the decision of the last step. If the state sk of the Kth stage and the decision uk(sk) are sure. Then the state Sk+1 of the K+1th stage is also completely determined.
State transition equation method for dynamic programming problems
The state transition equation method is somewhat similar to recursive problem-solving. We need to analyze how to solve a problem recursively through subproblems, also called the optimal substructure. The recursive formula is written based on the optimal substructure, which is also known as the state transition equation. With the state transition equation, the code implementation is straightforward. In general, we have two code implementations. One is recursive with “memoization,” and the other is iterative recursion.
It is important to note that the state t transition equation is the key to solving dynamic programming.