## 编程知识 cdmana.com

### Thinking private school -- Dynamic Planning

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=grid

• A final state

The final state is when we're done dp[m-1][n-1]. 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.length;
//dp[i][j] From grid 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 thumbs-up 、 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

https://cdmana.com/2021/02/20210201004317210K.html

Scroll to Top