931. The descent path is the smallest and

One 、 subject

Original link ：931. The descent path is the smallest and

1. Title Description

To give you one n x n Of square An array of integers matrix , Please find out and return through matrix Of descent path Of Minimum and .

descent path You can start with any element in the first line , And select an element from each row . The element selected in the next row is at most one column apart from the element selected in the current row （ That is, the first element directly below or diagonally left or right ）. say concretely , Location (row, col) The next element of should be (row + 1, col - 1)、(row + 1, col) perhaps (row + 1, col + 1) .

Example 1：

 Input ：matrix = [[2,1,3],[6,5,4],[7,8,9]]
 Output ：13
 explain ： As shown in the figure , And the smallest two descent paths 

Example 2：

 Input ：matrix = [[-19,57],[-40,-5]]
 Output ：-59
 explain ： As shown in the figure , Is the minimum descent path 

Tips ：

• n == matrix.length == matrix[i].length
• 1 <= n <= 100
• -100 <= matrix[i][j] <= 100

2. Basic framework

C++ The basic framework code is as follows :

int minFallingPathSum(vector<vector<int>>& matrix) {
    
}

3. Their thinking

• Topic analysis

1. The goal of the problem is to find the minimum sum of the descent path , It belongs to the minimum value problem .

2. From i Any element in the row can only be summed in the downward direction .

3. (i,j) The square can drop to (i,j - 1)、(i, j) or (i,j + 1) Of diamonds .

4. It can be concluded that the recurrence formula is ：

   martrix[i][j] += min{martrix[i - 1][j - 1], martrix[i - 1][j], martrix[i - 1][j + 1]}

5. When j = 0 Or j = matrix.size() - 1 when , It needs to be dealt with separately ：

   • j = 0, Only from the upper layer j and j + 1 To come over .
   • j = matrix.size() - 1, Only from the upper layer j - 1 and j To come over .
   • If only exist j = 1 Of matrix Array , namely j = matrix.size() - 1 = 0, Then only from the upper layer j Come down .

6. Sort the last row once , Choose the smallest path and .

• Implementation code ：

  int minFallingPathSum(vector<vector<int>>& matrix) {
        
      int i, j;
      for (i = 1; i < matrix.size(); i++)
      {
        
          for (j = 0; j < matrix[i].size(); j++)
          {
        
              if (j == 0 && j == matrix[i].size() - 1) matrix[i][j] += matrix[i - 1][j];
              else if (j == 0) matrix[i][j] += min(matrix[i - 1][j], matrix[i - 1][j + 1]);
              else if (j == matrix[i].size() - 1) matrix[i][j] += min(matrix[i - 1][j - 1], matrix[i - 1][j]);
              else
                  matrix[i][j] += min(matrix[i - 1][j - 1], min(matrix[i - 1][j], matrix[i - 1][j + 1]));
          }
      }
      sort(matrix[i - 1].begin(), matrix[i - 1].end());
      return matrix[i - 1][0];
  }