编程知识 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 :

image

  • 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[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[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 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

版权声明
本文为[The fox]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/02/20210201004317210K.html

Scroll to Top