The finger of the sword Offer II 099. Sum of minimum paths

One 、 subject

Original link ： The finger of the sword Offer II 099. Sum of minimum paths

1. Title Description

Given a... That contains a nonnegative integer m x n grid grid , Please find a path from the top left corner to the bottom right corner , Make the sum of the numbers on the path the smallest . explain ： A robot can only move down or right one step at a time .

• Example 1：

  Input ：grid = [[1,3,1],[1,5,1],[4,2,1]]
  Output ：7
  explain ： Because the path 1→3→1→1→1 The sum of is the smallest .

• Example 2：

  Input ：grid = [[1,2,3],[4,5,6]]
  Output ：12

• Tips ：

  m == grid.length
  n == grid[i].length
  1 <= m, n <= 200
  0 <= grid[i][j] <= 100

2. Basic framework

C++ The basic framework code is as follows :

int minPathSum(vector<vector<int> >& grid){
    
}

3. Their thinking

• Topic analysis

1. The goal of the topic is to return the minimum sum of numbers on the path from the upper left corner to the lower right corner .
2. This problem is the problem of finding the best value , Dynamic programming can be considered .
3. except 0 That's ok 0 Outside the column dp[i][j] May by dp[i - 1][j] or dp[i][j - 1] Turn around , So the recursive formula we can get is ：dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
4. dp[i][j] Express i,j The sum of the minimum paths taken by the current position .
5. because dp[i][j] State by dp[i - 1][j] and dp[i][j - 1] Transfer from , We need to i by 0 and j by 0 These two cases are initialized .
6. i = 0 When , It means there is only one path , therefore i = 0 Each column in this row is initialized as the numerical cumulative sum of the current path from left to right ,j = 0 Each row in this column should also be initialized as the numerical sum of the path from top to bottom .

• Implementation code ：

  int minPathSum(vector<vector<int>>& grid) {
        
      int m = grid.size();
      int n = grid[0].size();
      vector<vector<int> > dp(m, vector<int>(n));
      dp[0][0] = grid[0][0]; //  initialization (0,0) Minimum value of position 
      for (int i = 1; i < m; i++)	//  Initializing page 0 Column Division (0,0) Path and minimum value of position 
          dp[i][0] = grid[i][0] + dp[i - 1][0];
      for (int j = 1; j < n; j++) // //  Initializing page 0 Row Division (0,0) Path and minimum value of position 
          dp[0][j] = grid[0][j] + dp[0][j - 1];
      for (int i = 1; i < m; i++)
          for (int j = 1; j < n; j++)
              dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
      return dp[m - 1][n - 1];
  }