This article is participating in the “Java Theme Month – Java brush questions clock”, see < activity links > for more details.

【Java brush questions punch card 】 Brushing questions is much better than playing games, and the sense of achievement is getting stronger and stronger. I insist on brushing several questions every day, exercising for 30 minutes every day, waiting for 8-block abs and waiting for offers from big factories.

Then do it! This column is all about dynamic planning, I will start from the shallow to the deep, step by step, brush questions is such a need for continuous memory – Ebbinghaus memory method 2121112. There isn’t much about dynamic programming, but it’s a must for every programmer


This is a classic 😄😄😄 \color{green}{😄 😄 😄 ~}

What problem can I choose to do dynamic programming?

Counting 1.

  • How many ways can I get to the bottom right corner
  • How many ways can I pick the sum of k numbers yes is sum

2. Find the maximum and minimum

  • The maximum numeric sum of the path from the upper left corner to the lower right corner
  • Maximum ascending subsequence length

3. Seek existence

  • Stone game, whether the first hand will win
  • Can we pick k numbers such that the sum is sum

Leecode 64. Minimum path sum

Given an M x N grid with non-negative integers, find a path from the top left to the bottom right that minimizes the sum of the numbers along the path.

Note: you can only move one step down or right at a time.

 

Example 1:

Input: the grid = [,3,1 [1],,5,1 [1], [4, 2, 1]] output: 7 explanation: because the path 1-3-1-1-1 the sum of the minimum. Example 2:

Input: grid = [[1,2,3],[4,5,6]] output: 12

Tip:

m == grid.length

n == grid[i].length

1 <= m, n <= 200

0 <= grid[i][j] <= 100

Look at the previous problem solution, think about it, here we use dynamic programming to solve the problem, consider the following points:

  1. Boundary processing
  2. Intermediate path
  3. This is going to be M times N times so we’re going to be comparing each of these boxes, and we’re just going to take a smaller value

Dp said [I] [j] from the upper left corner to (I, j) (I, j) position of minimum path and the initial conditions: dp [0] [0] = grid [0] [0]

When I >0 and j=0, dp[I][0]= DP [i-1][0] + grid[I][0]; / / the grid [I] [0] is finally the value of a grid when I = 0 j > 0 dp [0] [1] = dp [0] [1] + grid [0] [j]; When I j > > 0 0 dp [I – 1] [1] = min (dp [j], [I – 1] dp [I]] [j – 1) + grid [I] [j];

Reference code:

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length, columns = grid[0].length;
        int[][] dp = new int[rows][columns];
        dp[0] [0] = grid[0] [0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1] [0] + grid[i][0];
        }
        for (int j = 1; j < columns; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; }}return dp[rows - 1][columns - 1]; }}Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️