Optimization method of path problem before dynamic planning

Path problem before Dynamic Planning

routing problem ： This chapter talks about the minimum path sum of triangles （Leetcode 120 secondary ）、 The descent path is the smallest and (Leecode 931 secondary ）、 The descent path is the smallest and II（Leedcode 1289 difficult ）

---

---

Preface

Path problem is the prequel of knapsack problem as a classical dynamic programming problem , For understanding dp The thought model of dynamic programming . This article focuses on when the problem is complex , How to find the transfer equation 、 Optimize space 、 Time complexity

---

Tips ： The following is the main body of this article , The following cases can be used for reference

One 、 The minimum path of a triangle and （Leetcode 120 secondary ）

1. Problem description

Given a triangle triangle , Find the smallest sum from the top down .
Each step can only move to adjacent nodes in the next row . Adjacent nodes What I mean here is Subscript And The upper node subscript Equal to or equal to The upper node subscript + 1 Two nodes of . in other words , If it is in the subscript of the current line i , So the next step is to move to the subscript of the next line i or i + 1 .

2. Problem analysis

This problem is converted from the rectangle of the previous calculation path to a triangle , Then you can traverse only the upper triangle or the lower triangle .

2.1 Define the data structure

The question is how many different paths , In this case, you should use dp[m-1][n-1] To express the final result , This is no different from the above

2.2 Interpretation of structural meaning

In this question dp[i][j] It can be interpreted as ：i Represents the row of the map ,j Representative column

2.3 Establishment of state transition equation

In this question ：
Here's the picture , The map is a triangle and defines adjacent nodes , So we can only move down or to the lower right corner , So we follow 「 Current optional direction 」 Analyze ：
Current location can only 「 Down 」 Move , That is to say dp[i][j] = dp[i-1][j]+grid[i][j]
Current location can only 「 Lower right 」 Move , That is to say dp[i][j] = dp[i-1][j-1]+grid[i][j]
The current position can 「 Down 」 Can also 「 Lower right 」 Move , That is to say dp[i][j] =min（dp[i-1][j]+triangle[i][j],dp[i-1][j-1]+triangle[i][j]）
Derivation process ：
dp[i][j] It represents the arrival map grid[i][j] The path and of the point arrival path , Then step up ： How to get there grid[i][j] spot , There are only two ways ： Enter this point from the front point down or to the right , So arrive at grid[i][j] And only arrive dp[i][j-1] And + triangle[i][j]、dp[i-1][j-1]+triangle[i][j] Two possible , And take the smaller one , From this we can deduce dp[i][j] State transfer equation of ：dp[i][j] =min（dp[i-1][j]+triangle[i][j],dp[i-1][j-1]+triangle[i][j]）

3. Code display ：

The code is as follows （ Example ）：

class Solution {
    
public:
    int minimumTotal(vector<vector<int>>& triangle) {
    
        
        int m=triangle.size();
        int n=triangle[m-1].size();
        vector<vector<int>> dp(m, vector<int>(n));
        dp[0][0]=triangle[0][0];
        for(int i=0;i<m;i++)
        {
    
            for(int j=0;j<=i;j++)
            {
    
                if(i-1>j||i-1==j)
                {
    
                    if(i>0&&j>0)
                    {
    
                        dp[i][j]=min(dp[i-1][j]+triangle[i][j],dp[i-1][j-1]+triangle[i][j]);
                    }
                    else if(i>0)
                    {
    
                        dp[i][j]=dp[i-1][j]+triangle[i][j];
                    }
                }
                else
                {
    
                    if(i>0&&j>0)
                    {
    
                        dp[i][j]=dp[i-1][j-1]+triangle[i][j];
                    }
                }
            }
        }
        int minSum=dp[m-1][0];
        for(int i=1;i<n;i++)
        {
    
            if(dp[m-1][i]<minSum)
            {
    
                minSum=dp[m-1][i];
            }
        }
        return minSum;
    }
};

4. upgrade ： optimization algorithm

In the process of recursion, we find , Actually, the first one is i+1 The value of the row will only depend on i The result of that , Therefore, in space, you can only apply 2*n. As shown in the figure below ： For example, the calculated result in the first row is placed in the first row of the two-dimensional array , The second line is placed on the second line according to the result of the first line , When calculating the result of the third line , At this time, the result of the first line is invalid , Therefore, the result of the third row can be used to overwrite the data of the first row .

5. Code display of Optimization Algorithm

The code is as follows （ Example ）：

class Solution {
    
public:
    int minimumTotal(vector<vector<int>>& triangle) {
    
        
        int m=triangle.size();
        int n=triangle[m-1].size();
        vector<vector<int>> dp(2, vector<int>(n));
        dp[0][0]=triangle[0][0];
        for(int i=0;i<m;i++)
        {
    
            for(int j=0;j<=i;j++)
            {
    
                if(i-1>j||i-1==j)
                {
    
                    if(i>0&&j>0)
                    {
    
                        dp[i&1][j]=min(dp[(i-1)&1][j]+triangle[i][j],dp[(i-1)&1][j-1]+triangle[i][j]);
                    }
                    else if(i>0)
                    {
    
                        dp[i&1][j]=dp[(i-1)&1][j]+triangle[i][j];
                    }
                }
                else
                {
    
                    if(i>0&&j>0)
                    {
    
                        dp[i&1][j]=dp[(i-1)&1][j-1]+triangle[i][j];
                    }
                }
            }
        }
        int minSum=dp[(m-1)&1][0];
        for(int i=1;i<n;i++)
        {
    
            if(dp[(m-1)&1][i]<minSum)
            {
    
                minSum=dp[(m-1)&1][i];
            }
        }
        return minSum;
    }
};

Two 、 The descent path is the smallest and (Leecode 931 secondary ）

1. Problem description

To give you one n x n Of square An array of integers matrix , Please find out and return through matrix The 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) .

2. Problem analysis

This problem is transformed from the triangle of the calculation path of the previous problem into a rectangle , This time, the upgraded algorithm is directly used for analysis

2.1 Define the data structure

The question is how many different paths , In this case, you should use dp[m-1][n-1] To express the final result , This is no different from the above

2.2 Interpretation of structural meaning

In this question dp[i][j] It can be interpreted as ：i Represents the row of the map ,j Representative column

2.3 Establishment of state transition equation

Here's the picture , The map defines the adjacent nodes , So we can only move down or to the lower right corner or the lower left corner , So we follow 「 Current optional direction 」 Analyze ：
Current location can only 「 Down 」 Move , That is to say dp[i][j] = dp[i-1][j]+matrix[i][j]
Current location can only 「 Lower left 」 Move , That is to say dp[i][j] = dp[i-1][j+1]+matrix[i][j]
Current location can only 「 Lower right 」 Move , That is to say dp[i][j] = dp[i-1][j-1]+matrix[i][j]
The current position can 「 Down 」 Can also 「 Lower right 」 Move , That is to say dp[i&1][j]=min(dp[(i-1)&1][j-1],min(dp[(i-1)&1][j],dp[(i-1)&1][j+1]))+matrix[i][j];

2.4. Code display ：

The code is as follows （ Example ）：

class Solution {
    
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
    
        int n=matrix.size();
        vector<vector<int>>dp(2,vector<int>(n,0));
        dp[0][0]=matrix[0][0];
        for(int i=0;i<n;i++)
        {
    
            for(int j=0;j<n;j++)
            {
    
                if(i==0)
                {
    
                    dp[i][j]=matrix[i][j];
                }
                else
                {
    
                    if(j!=0&&j!=n-1)
                    {
    
                        dp[i&1][j]=min(dp[(i-1)&1][j-1],min(dp[(i-1)&1][j],dp[(i-1)&1][j+1]))+matrix[i][j];
                    }
                    if(j==0)
                    {
    
                        dp[i&1][j]=min(dp[(i-1)&1][j],dp[(i-1)&1][j+1])+matrix[i][j];
                    }
                    if(j==n-1)
                    {
    
                        dp[i&1][j]=min(dp[(i-1)&1][j-1],dp[(i-1)&1][j])+matrix[i][j];
                    }
                }
            }
        }
        int res = dp[(n-1)&1][0];
        for (int i = 0; i < n; i++) res = min(res, dp[(n - 1)&1][i]);
        return res;
    }
};

Two 、 The descent path is the smallest and II(Leecode 1289 difficult ）

1. Problem description

To give you one n x n Integer matrix arr , Please return Nonzero offset descent path The minimum value of the sum of numbers .
Nonzero offset descent path Defined as ： from arr Select a number for each row in the array , And in the numbers selected in order , Adjacent numbers are not in the same column of the original array .

2. Problem analysis

The difference between this problem and the previous one is , The first i+1 Line can be from i Come from any position of the line , Except for the same column . First, solve according to the original idea , Then we'll talk about how to optimize ：

2.1 Define the data structure

The problem is all paths and , In this case, you should use dp[m-1][n-1] To express the final result , This is no different from the above

2.2 Interpretation of structural meaning

In this question dp[i][j] It can be interpreted as ：i Represents the row of the map ,j Representative column

2.3 Establishment of state transition equation

There is no fixed direction here , Therefore, you need to traverse the previous row except all the values of the same column ：dp[i][j]=min(dp[i-1][0],dp[i-1][1]…dp[i-1][n])+arr[i][j];

3. Code display ：

The code is as follows （ Example ）：

class Solution {
    
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
    
        int n=grid.size();
        vector<vector<int>>dp(2,vector<int>(n,0));
        dp[0][0]=grid[0][0];
        for(int i=0;i<n;i++)
        {
    
            for(int j=0;j<n;j++)
            {
    
                if(i==0)
                {
    
                    dp[i][j]=grid[i][j];
                }
                else
                {
    
                   
                        int br=INT_MAX;
                        for(int m=0;m<n;m++)
                        {
    
                            if(m!=j){
    
                                br=min(br,dp[(i-1)&1][m]);
                            }
                        }
                        dp[i&1][j]=br+grid[i][j];
                    
                    
                }
            }
        }
        int res = dp[(n-1)&1][0];
        for (int i = 0; i < n; i++) res = min(res, dp[(n - 1)&1][i]);
        return res;
        
    }
};

4. upgrade ： optimization algorithm

In the process of recursion, we find , Actually, the first one is i+1 The value of the row will only depend on i Minimum and sub minimum values of rows , When the minimum value is in the same column as the current column , Only the second lowest value can be selected , Otherwise, choose the minimum . So in the process of calculation , You only need to define two temporary variables to save the minimum value and sub minimum value of the previous row . These two values in the first row are treated separately .

5. Code display ：

The code is as follows （ Example ）：

class Solution {
    
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
    
        int n=grid.size();
        int dp[n][n];
        dp[0][0]=grid[0][0];
        int _min=-1;
        int _Maxmin=-1;
         for (int i = 0; i < n; i++) {
    
            int val = grid[0][i];
            dp[0][i] = val;
            if (val < (_min == -1 ? INT_MAX : dp[0][_min])) {
    
                _Maxmin = _min;
                _min = i;
            } else if (val < (_Maxmin == -1 ? INT_MAX : dp[0][_Maxmin])) {
    
                _Maxmin = i;
            }
        }
        for(int i=1;i<n;i++)
        {
     
            
            int min=-1;
            int Maxmin=-1;
            for(int j=0;j<n;j++)
            {
    
                dp[i][j] = INT_MAX;
                if(j!=_min)
                {
    
                     dp[i][j]=dp[i-1][_min]+grid[i][j];
                }
                else{
    
                    dp[i][j]=dp[i-1][_Maxmin]+grid[i][j];
                } 
                if (dp[i][j] < (min == -1 ? INT_MAX : dp[i][min])) {
    
                    Maxmin = min;
                    min = j;
                } else if (dp[i][j] < (Maxmin == -1 ? INT_MAX : dp[i][Maxmin])) {
    
                    Maxmin = j;
                }
            }
            _min=min;
            _Maxmin=Maxmin;
        }
        int res = dp[(n-1)][0];
        for (int k = 0; k < n; k++) res = min(res, dp[(n - 1)][k]);
        return res;
    }
};

summary

This paper mainly focuses on the optimization method in the state transition equation , It mainly analyzes whether i+1 Is the row related to all the previous rows or only the previous row .leecode 931 We can analyze that the current line is only related to the previous line , Therefore, the space complexity can be optimized nxn–>2*n,leecode 1289 We can find that the current row is only related to the minimum value of the previous row and this minimum value , Therefore, the time complexity is determined by n The cubic optimization of is n The square of . The following statistics all feasible paths （ difficult ）【 Memory search 】, Because it is difficult to solve it directly from dynamic programming , So learn first DFS, In from dfs Convert to dynamic programming . The next chapter begins DFS Learning from , If you have achieved something, you can solve this problem again .