I'm brushing my finger offer and LeetCode Found in , Dynamic programming is a common problem , Then, let's carefully analyze and summarize the routine .
Introduce
Dynamic programming （DP） To put it bluntly, it is actually a method to solve the optimal solution , It's a rather special idea of divide and rule , It can be used to optimize the time complexity , It is mainly based on the state transfer equation to solve .
It contains two main ideas: divide and conquer and greed .
Their thinking
Generally speaking, there are four steps to solve the problem of dynamic programming ：
 State means
 Transfer equation
 The initial state
 A final state
Let's explain these four steps in detail , In the beginning, we need to build a table to store data , Most of them use arrays , Then find out the existing state transfer equation by analyzing the problem , How does it change from the previous state to the next state , Then set our initial value according to the topic , And then repeat the calculation according to the state transfer equation , In this process, the accumulated records of the previous area are used , So it can speed up . Finally, keep looking for the final state we need .
Real exercises
Let's take the sword finger here offer No 47 The maximum value of the gift is a typical example to let you understand the idea of this algorithm
The maximum sum of successive subarrays
subject ：
In a m*n There is a gift in every space of the chessboard , Every gift has a certain value （ Value greater than 0）. You can start from the top left corner of the chessboard to get the gifts in the grid , And move right or down one space at a time 、 Until you reach the bottom right corner of the chessboard . Given the value of a chessboard and its gifts , Please calculate the maximum value of gifts you can get ？
solution
This paper is to explain the dynamic programming, and it is sure to use dynamic programming to solve this problem . Then we'll follow our steps
 State means
Let's set the dynamic programming matrix dp[][], among dp[i][j] From the upper left corner of the chessboard to the cell (i,j) The maximum cumulative value of a gift when you get it
 Transfer equation
Because you can only move right or down , therefore ：

 When i=0 And j=0, Is the starting element
 When i=0 And j≠0, For the first line of elements , It's only on the left
 When i≠0 And j=0, For the first column of elements , It's only up to
 When i≠0 And j It's not equal to 0, It can be reached from the top or left
therefore , The state transfer equation is as follows ：
 The initial state
From the above analysis, we can know dp[0][0]=grid[0][0]
 A final state
The final state is when we're done dp[m1][n1]. return dp The element in the lower right corner of the array
java Realization
With the idea, it's behind java The implementation of the , As shown below ：
class Solution {
public int maxValue(int[][] grid) {
int row = grid.length;
int column = grid[0].length;
//dp[i][j] From grid[0][0] To grid[i  1][j  1] The greatest value of time
int[][] dp = new int[row + 1][column + 1];
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= column; j++) {
dp[i][j] = Math.max(dp[i  1][j], dp[i][j  1]) + grid[i  1][j  1];
}
}
return dp[row][column];
}
}
summary
That's all dynamic programming is about , As one in LeetCode Questions that often appear in interviews , It can be said that we have to master it . In short, focus on four things ：
 State means
 Transfer equation
 The initial state
 A final state
The most difficult one is the transfer equation , This should be handled flexibly according to various topics , Or do more topic summary can also get good harvest and progress . As long as you have the state transfer equation , If we pay more attention to the initial state and boundary value, there will be no big problem .
Last
 If you think you've got something to watch , Hope to pay attention to , By the way, give me a compliment , This will be my biggest motivation to update , Thank you for your support
 Welcome to my official account 【java Grave Fox 】, Focus on java And Computer Basics , I'm sure you'll get something from it , I don't believe you hit me
 Ask for one key and three links ： give the thumbsup 、 forward 、 Looking at .
 If you have different opinions or suggestions after reading , Welcome to comment and exchange with us . Thank you for your support and love .
—— I'm Suzuka fox , I love programming as much as you do .
Welcome to the official account “ Java Grave Fox ”, Get the latest news
版权声明
本文为[The fox]所创，转载请带上原文链接，感谢
https://cdmana.com/2021/02/20210201004317210K.html