Leetcode 931: minimum sum of descent path

link

Ideas ：

Substructure ：
about matrix[i][j], Only possible from matrix[i-1][j], matrix[i-1][j-1], matrix[i-1][j+1] These three Transfer a position .

that , Just know to arrive (i-1, j), (i-1, j-1), (i-1, j+1) The upper layer contains three elements that may be passed in Minimum path sum , + matrix[i][j] The value of the element , Can calculate the arrival position (i, j) The most ⼩ Path and ;

Ideas ：

1. dp Definition of function ： From ⼀⾏（matrix[0][j]） Fall to , Fall into position matrix [i][j] The minimum path sum of is dp(matrix, i, j).
2. dp Parameters of matrix[i][j] The element is state ;
3. To matrix[i][j] The minimum sum result of is decomposed into the upper layer (i-1, j), (i-1, j-1), (i-1, j+1) Three Substructure , The subproblems are independent of each other ;
4. Overlapping subproblems ： matrix[i][j] Will be used repeatedly , If calculated （i,j） need (i-1, j), (i-1,j-1), (i-1,j+1) , And count （i,j+1） need (i-1,j+1),(i-1,j), (i-1,j+2), There is (i-1,j), (i-1,j+1) Repeated calculations ！

Violent recursive solution ：

class Solution {
    
    public int minFallingPathSum(int[][] matrix) {
    
        int n =matrix.length;
        int res=Integer.MAX_VALUE;

        //  Traverse all columns of the last row , dp Function returns the second j The minimum path of the column and 
        for(int j=0;j<n;j++){
    
            res=Math.min(res,dp(matrix,n-1,j)); //  Pass in dp The state parameter of is each element in the last line , Calculate the minimum result is the desired 
        }
        return res;
    }


    int  dp(int[][] matrix,int i,int j){
    	
		// base case
        //  Two dimensional array out of bounds returns the maximum value , Can't get 
        if(i<0 ||j<0 || 
        i>=matrix.length || 
        j>=matrix[0].length){
       
            return Integer.MAX_VALUE;
        }

        if(i==0){
     //  There is only one line 
            return matrix[0][j];
        }

        //  State transition equation , Return to the current line  j  The minimum path of the column and 
        //  result  =  Recursively find the minimum path sum of each state parameter in turn  +  Current node element value 
        int sub=matrix[i][j]+min(dp(matrix,i-1,j),dp(matrix,i-1,j-1),dp(matrix,i-1,j+1));
        return sub;
    }
    

    int min(int a,int b,int c){
    
        return Math.min(a,Math.min(b,c));
    }
}

Imagine that the first node of the recursive tree is The last line of the two-dimensional array , But the first layer of the tree has n Nodes instead of a root node , So you need to be in main To traverse the last row of the array in turn Every element ;
Two dimensional array every layer up , The node of the tree recursively goes down once ,
After reaching the first floor （ Recursion to i=0 The bottom of the tree ） from base case return matrix [0][j] , Then put each layer min The results of are passed back to the last line in turn matrix [n-1][j] That is, the first layer of the tree

Using recursion + Memorandum ：

class Solution {
    
    int[][] memo;
    public int minFallingPathSum(int[][] matrix) {
    
        int n =matrix.length;
        int res=Integer.MAX_VALUE;
        // dp Array means from the first line to  matrix[i][j] Minimum sum of 
        memo=new int[n][n]; 
        for(int i=0;i<n;i++){
     //  Because the minimum is required , Need to put memo Initialize to unreachable large 
            Arrays.fill(memo[i],Integer.MAX_VALUE); //  Initialize each element of each row 
        }
        for(int j=0;j<n;j++){
     //  Traverse all the elements in the last line （ state ）
            res=Math.min(res,dp(matrix,n-1,j));
        }
        return res;
    }


    int  dp(int[][] matrix,int i,int j){
    
        // The two-dimensional array is out of bounds 
        if(i<0 ||j<0 || 
        i>=matrix.length || 
        j>=matrix[0].length){
       
            return Integer.MAX_VALUE;
        }
        // base case
        if(i==0){
     //  There is only one line 
            return matrix[0][j];
        }
        //  Overlapping subproblems 
        if(memo[i][j]!=Integer.MAX_VALUE){
    
            return memo[i][j]; //  If it has been calculated, it returns the minimum sum 
        }
        //  State transition equation 
        memo[i][j]=matrix[i][j]+min(dp(matrix,i-1,j),dp(matrix,i-1,j-1),dp(matrix,i-1,j+1));
        return memo[i][j];
    }

    int min(int a,int b,int c){
    
        return Math.min(a,Math.min(b,c));
    }
}

Add ：
For example, the complexity of our algorithm is O(NlogN), Think about how you can get ⼀ Logarithmic complexity ？ Definitely ⽤ To ⼆ Sub search perhaps ⼆ Fork tree related data structures ,⽐ Such as TreeMap,PriorityQueue Something like that, right . Again ⽐ Such as , Sometimes questions ⽬ The time complexity of your algorithm is O(MN), What can this be associated with ？ Sure ⼤ Dare to guess , The conventional solution is ⽤ Backtracking algorithm Violent ⼒ Exhausting , But a better solution is dynamic programming ,⽽ And is ⼀ individual ⼆ Dimensional dynamic programming , need ⼀ individual M * N Of ⼆ dimension dp Array , So produce ⽣ That's it ⼀ A time complexity .