LeetCode — Minimum path sum (dynamic programming)

Topic describes

Their thinking

This topic is a classic example of dynamic programming, is a must master exercise.

1. DP equation of the core

$dp[i][j] = dp[i][j] + Math.min(dp[i-1][j],dp[i][j-1]) + dp[i][j]$

2. Dealing with boundary conditions

And they tell us explicitly that when you move, you can only move to the right or down, and nothing else is allowed, so for the first row, you can only move from left to right, and for the first column, you can only move from up to down.

• How to handle the first line

for (let j = 1; j < grid[0].length; j++) {
    grid[0][j] = grid[0][j] + grid[0][j - 1];
}
Copy the code

• The treatment of the first column

for (let i = 1; i < grid.length; i++) {
    grid[i][0] = grid[i][0] + grid[i - 1] [0];
}
Copy the code

3. Dealing with general cases

The general case is to use the core DP equation from our first step.

AC code

var minPathSum = function (grid) {
  // This topic is a classic example of dynamic programming
  Subject at the core of the dynamic equation for: / / dp [I] [j] = math.h min (dp [j], [I - 1] dp [I]] [j - 1) + dp [I] [j].
  // First, we deal with the boundary conditions. The problem explicitly states that each movement can only move to the right or down, so no movement can be made to the left or any other direction.
  // Process the element in the first line: the element in the first line does not have the upper item, starting with the second element in the first line
  for (let j = 1; j < grid[0].length; j++) {
    grid[0][j] = grid[0][j] + grid[0][j - 1];
  }
  // Handle the elements in the first column in the same way as the elements in the first row
  for (let i = 1; i < grid.length; i++) {
    grid[i][0] = grid[i][0] + grid[i - 1] [0];
  }
  // Handle general cases
  for (let i = 1; i < grid.length; i++) {
    for (let j = 1; j < grid[0].length; j++) {
      grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]; }}return grid[grid.length - 1][grid[0].length - 1]};Copy the code

The title to reflect

• Learn to use dynamic programming to solve path problems.

• It is very important to deal with boundary conditions in dynamic programming.