Viewing dynamic programming from a written test

Viewing dynamic programming from a written test

For most people who learn programming, dynamic programming has always been a difficult point to break through. I am also very confused in the process of learning. I have watched a lot of books, materials and videos, and I can understand the basic ideas. But when I encountered a problem, I still felt unable to start . Recently, when I was doing a written test, I suddenly lost my understanding. I will record my simple understanding here, so that everyone passing by can give pointers.

Reverse Thinking

The topic is as follows:

A person walking on m n squares can only go to the right or down at a time. The value of each square is the distance. Find the shortest path value from the starting point to the ending point . Example: 3 3 1 3 1 1 5 1 4 2 1 The final output is 7, and the shortest distance it takes to walk from the upper left to the lower right is 7

When I first saw the question, I knew it was a dynamic programming question. However, due to the various (tai) types (cai) and the original (le) cause, I still could not solve the problem. I have seen a lot of topics. There is a kind of rush that I am familiar with but it doesn't wait to see me. When it's over, look back and think, think, think, think... Half an hour has passed, and then think and think, finally the code is realized.

According to normal thinking, if a person stands at the starting point and walks to the right or down to the end, then the shortest distance is to compare the distance to the left or down each time, take the smallest distance, and add the distance required by oneself. In this way, walking to the end is the shortest path value. Verification against the title, that is 1 -> (down) 1 -> (down) 4 -> (right) 2 -> (right) 1 To reach the end point, the total distance is 9, found this way of walking Is wrong. The correct way to move should be 1 -> 3 -> 1 -> 1 -> 1, and the total distance is 7 the shortest.

This method does not work, then let's consider the second solution. Now, I don t calculate from the starting point, because when we look at the matrix of the past problem, we know that with this input, the best path is 1 -> 1 -> 1 -> 3 -> 1 This way, how to get it What about? We can see from the last number of the matrix that it is the end point. How did this end point come over? It is found that it comes from the number on the left or above, why is it so? Because the title says, you can only go to the right or down, so this position of the end point can either be reached by going down from the upper position, or by going to the right from the left position. So we deduce 1 -> 1 -> 1 -> 3 -> 1 from the back to the front. As shown below:

This is the legendary dynamic programming . In this question, a state we define is f(i, j), which means the shortest path taken from the starting point to the coordinates (i, j), which can be found by the above inference , The shortest path of coordinates (i, j) is always derived from the minimum of coordinates (i-1, j) and coordinates (i, j-1) plus the value of coordinates (i, j) itself , state transition The equation is f(i, j) = Math.min(f(i-1 ,j), f(i, j-1)) + values[i, j]i, j is the coordinates of the two-dimensional array, and values are the initial values of the corresponding coordinates of the array. The estimated values of the original array values and dp array are as follows:

With the above foreshadowing, we can get the code:

function solve(arr, m, n) {
   // dp , dp[i][j] i,j 
    var dp = new Array(m);
    for (var i = 0; i < m; i++) {
        dp[i] = [];
        for (var j = 0; j < n; j++) {
            dp[i][j] = 0;
        }
    }
   // 
    dp[0][0] = arr[0][0];
    for (var i = 1; i < n; i++) {
        dp[0][i] = arr[0][i] + dp[0][i - 1];
    }
    for (var i = 1; i < m; i++) {
        dp[i][0] = arr[i][0] + dp[i - 1][0];
    }
   // 
    for (var i = 1; i < m; i++) {
        for (var j = 1; j < n; j++) {
            dp[i][j] = arr[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m - 1][n - 1];
}
 

We use a two-dimensional array dp to store the shortest path value of each node. It is important to note here that the first row and first column of the array need to be initialized. Each point in the first row can only be from the left Go to the right, so you can directly accumulate the values of the corresponding coordinates; in the same way, each point in the first column can only go from the top to the bottom, and each point can be added to the value of one point from the original value. Next, start from row 1, column 1, and traverse to m -1, n -1, and fill in each state value. The return value of the function is the coordinates of the end point, which is dp[m-1][ n-1].

The idea of dynamic programming

When I was learning dynamic programming, I was stunned to learn about the optimal sub-structure, no side effects, repeated sub-problems, etc., looking at these theories seem to understand.

What is dynamic programming? I think that dynamic programming is the reverse. To derive such a process from back to front is like opening up the perspective of God. When the results are already known, through the choices of various situations, the original starting point is derived, and then Define a reasonable state to explain. Like the question above, ask you the shortest distance from the upper left corner to the lower right corner alone. When we look at the question, we can see the distance value of each path and the distribution of the surrounding paths globally, so we can calculate The results are quickly obtained. The first solution above is actually a greedy way of thinking. Starting from the starting point, choose the shortest path to go down each time. The disadvantage of this is that the path behind may be worse, and it is easy to get the best because of short-sightedness. the result of.

In general, when encountering some optimal problems, such as finding the shortest path, maximum value, longest common subsequence, etc., you must consider using dynamic programming to solve the problem, and sometimes you may wish to use greedy first Try to think about whether you can get the result, so that you can understand the reasons for the failure, and you can deepen the understanding of the application scenarios of dynamic programming.

postscript

Many times, if you understand it, you may not really understand it. As mentioned at the beginning, I know that the topic is dynamic programming, but I just feel that I can t start. Now I still need to do more and understand, and maybe I will have new insights in a while.

The understanding of this knowledge point needs to be deepened. Please correct me if there is anything wrong with the article. Welcome to exchange and discuss.

(Finish)