This is the 29th day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

“Given a grid, find a path that maximizes the sum of the numbers from the top left to the bottom right.”

Title link:

Source: LeetCode

Link: 64. Minimum Path and – LeetCode (leetcode-cn.com)

2

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: grid = [[1,3,1],[1,5,1],[4,2,1]] output: 7 explanation: because path 1→3→1→1 has the smallest sum.Copy the code
Example 2: input: grid = [[1,2,3],[4,5,6]] output: 12Copy the code

Second, the problem solving

1. Analysis of ideas

I’m not going to run this problem, so I’m going to use dynamic programming, but since we’re looking for a path with the largest sum of numbers, the path is unique.

For elements that are not in the first column of the first row, you can move one step from the previous element and the minimum path of the element is equal to the minimum value in the sum of the minimum path of the previous element plus the value of the current element.

2. Code implementation

Code reference:

public class Solution {
    public int MinPathSum(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        int[,] dp = new int[m + 1, n + 1];
        for (int i = 2; i <= m; i++) dp[i, 0] = int.MaxValue;
        for (int j = 2; j <= n; j++) dp[0, j] = int.MaxValue;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i, j] = Math.Min(dp[i - 1, j], dp[i, j - 1]) + grid[i - 1][j - 1]; }}returndp[m, n]; }}Copy the code

3. Time complexity

Time complexity: O(Mn)

Where M is the length of the grid and n is the width of the grid, the answer can be obtained by traversing the grid once.

Space complexity: O(Mn)

Where M is the length of the grid and n is its width.

Third, summary

The spatial complexity can be optimized to work in situ, that is, O1, but the data of the original matrix will be destroyed.

Through analysis, it can be found that when data is scanned matrix, the original data information is only used once in scanning and will not be used later.

Therefore, when scanning to write DP, you can directly overwrite it without affecting the final outcome.

That is, dp that uses memory allocated by the system for grid to record dynamic planning.