Maximum path and problem （ Cherry picking problem ）

author ：Grey

Original address : Maximum path and problem （ Cherry picking problem ）

Topic link

LeetCode 741. Pick cherries

Main idea

The difficulty of this question lies in trying , How to simulate a one-time situation , We can do that , Define two little people , Both of them started from (0,0) Set out , To the lower right corner , Each person chooses a different next step at the same time , If two little people jump to the same position , Count only one . Because two little people are walking at the same time , And only one step at a time , therefore , The two little men must have reached the lower right corner at the same time , The number of cherries collected by the two little people , It's the quantity collected at one time .

We can write the first trial version , Define recursive functions

int p(int[][] matrix, int m, int n, int x1, int y1, int x2, int y2)

The meaning of recursive function means , The first villain from (x1,y1) Start at the bottom right corner , The second villain from (x2,y2) Start at the bottom right corner , What is the maximum value obtained . therefore p(matrix, m, n, 0, 0, 0, 0) Is the answer we need .

Next, consider base case, namely ： Both little men reached the lower right corner , As the title has been said , The value in the lower right corner must not be -1, therefore , You can get a cherry quantity .

        if (x1 == m - 1 && y1 == n - 1) {
    
            //  We have reached the bottom right corner 
            //  Implied conditions ： The other point must also reach the lower right corner 
            //  Get a portion of cherries 
            return matrix[x1][y1];
        }

The next step is to try generally , It can be divided into the following four cases ：

situation 1： The first villain goes down , The second villain goes to the right .

situation 2： The first villain goes down , The second little man went down .

situation 3： The first villain goes to the right , The second little man went down .

situation 4： The first villain goes to the right , The second villain goes to the right .

But in any of these branches , Remember to meet two conditions

The first condition , Don't cross the border

The second condition , The next place to go cannot be -1, Because the title says ,-1 It's a place you can't walk .

        int next = -1;
        //  Next , Next 
        if (x1 + 1 < m && x2 + 1 < m && matrix[x1 + 1][y1] != -1 && matrix[x2 + 1][y2] != -1) {
    
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2 + 1, y2), next);
        }
        //  Next , Right 
        if (x1 + 1 < m && y2 + 1 < n && matrix[x1 + 1][y1] != -1 && matrix[x2][y2 + 1] != -1) {
    
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2, y2 + 1), next);
        }
        //  Right , Next 
        if (y1 + 1 < n && x2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2 + 1][y2] != -1) {
    
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2 + 1, y2), next);
        }
        //  Right , Right 
        if (y1 + 1 < n && y2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2][y2 + 1] != -1) {
    
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2, y2 + 1), next);
        }

After the above four branches , If next The value of the or -1, It means there is no way , return -1

        if (next == -1) {
    
            return -1;
        }

If next It's not equal to -1, It shows that there is a way to go , Then continue to judge whether the two villains are in the same position , If in the same location , Collect only one cherry , If it's not in the same place , Collect the sum of cherries where the two little people are .

        if (x1 == x2) {
    
            //  Arrive at the same location , Take only one value 
            return next + matrix[x1][y1];
        }
        return next + matrix[x1][y1] + matrix[x2][y2];

notes ： Judge the same position , You only need the same coordinates in one dimension .

Complete code

    public static int cherryPickup1(int[][] matrix) {
    
        return Math.max(0, p(matrix, matrix.length, matrix[0].length, 0, 0, 0, 0));
    }

    //  Define two little people , Both of them started from (0,0) Set out , To the lower right corner , Each person chooses a different next step at the same time , If two little people jump to the same position , Count only one .
    public static int p(int[][] matrix, int m, int n, int x1, int y1, int x2, int y2) {
    
        if (x1 == m - 1 && y1 == n - 1) {
    
            //  We have reached the bottom right corner 
            //  Implied conditions ： The other point must also reach the lower right corner 
            //  Get a portion of cherries 
            return matrix[x1][y1];
        }

        int next = -1;
        //  Next , Next 
        if (x1 + 1 < m && x2 + 1 < m && matrix[x1 + 1][y1] != -1 && matrix[x2 + 1][y2] != -1) {
    
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2 + 1, y2), next);
        }
        //  Next , Right 
        if (x1 + 1 < m && y2 + 1 < n && matrix[x1 + 1][y1] != -1 && matrix[x2][y2 + 1] != -1) {
    
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2, y2 + 1), next);
        }
        //  Right , Next 
        if (y1 + 1 < n && x2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2 + 1][y2] != -1) {
    
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2 + 1, y2), next);
        }
        //  Right , Right 
        if (y1 + 1 < n && y2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2][y2 + 1] != -1) {
    
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2, y2 + 1), next);
        }
        if (next == -1) {
    
            return -1;
        }
        if (x1 == x2) {
    
            //  Arrive at the same location , Take only one value 
            return next + matrix[x1][y1];
        }
        return next + matrix[x1][y1] + matrix[x2][y2];
    }

This solution is in LeetCode Upper direct timeout .

On the basis of the above attempts , We can do further optimization , The recursive function is now four mutable arguments , According to our design , In fact, we can get the following formula

x1 + y1 = x2 + y2

Then we can omit a parameter from the recursive function y2, because

y2 = x1 + y1 - x2

The above recursive method can be modified to

//  Omit y2 Parameters 
    public static int p(int[][] matrix, int m, int n, int x1, int y1, int x2) {
    
        if (x1 == m - 1 && y1 == n - 1) {
    
            //  We have reached the bottom right corner 
            //  Implied conditions ： The other point must also reach the lower right corner 
            //  Get a portion of cherries 
            return matrix[x1][y1];
        }

        int next = -1;
        //  Next , Next 
        if (x1 + 1 < m && x2 + 1 < m && matrix[x1 + 1][y1] != -1 && matrix[x2 + 1][getY2(x1, y1, x2)] != -1) {
    
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2 + 1), next);
        }
        //  Next , Right 
        if (x1 + 1 < m && getY2(x1, y1, x2) + 1 < n && matrix[x1 + 1][y1] != -1 && matrix[x2][getY2(x1, y1, x2) + 1] != -1) {
    
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2), next);
        }
        //  Right , Next 
        if (y1 + 1 < n && x2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2 + 1][getY2(x1, y1, x2)] != -1) {
    
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2 + 1), next);
        }
        //  Right , Right 
        if (y1 + 1 < n && getY2(x1, y1, x2) + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2][getY2(x1, y1, x2) + 1] != -1) {
    
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2), next);
        }
        if (next == -1) {
    
            return -1;
        }
        if (x1 == x2) {
    
            //  Arrive at the same location , Take only one value 
            return next + matrix[x1][y1];
        }
        return next + matrix[x1][y1] + matrix[x2][getY2(x1, y1, x2)];
    }
    public static int getY2(int x1, int y1, int x2) {
    
        return x1 + y1 - x2;
    }

We can do further optimization , Because the range of the three variable parameters is [0...m-1],[0...n-1],[0...m-1], Then we can set up three-dimensional dp, Cache all recursive results

int[][][] dp = new int[m][n][m];

The three dimensional dp The initial values for all positions of are set to Integer.MIN_VALUE, In recursive methods , Bring the 3D table into the parameter as a cache , During each recursion , First from dp Value in the table , If the value is not Integer.MIN_VALUE, Explain that this process has been calculated , Just take the value directly .

    public static int p(int[][] matrix, int m, int n, int x1, int y1, int x2, int[][][] dp) {
    
        if (dp[x1][y1][x2] != Integer.MIN_VALUE) {
    
            //  It shows that this process has been calculated , Take a value directly from the cache 
            return dp[x1][y1][x2];
        }
    }

Then in each recursion , Store the answer in the cache , The complete code is as follows

    //  Dynamic programming 
    //  3D table 
    public static int cherryPickup(int[][] matrix) {
    
        int m = matrix.length;
        int n = matrix[0].length;
        int[][][] dp = new int[m][n][m];
        for (int i = 0; i < m; i++) {
    
            for (int j = 0; j < n; j++) {
    
                for (int k = 0; k < m; k++) {
    
                    //  The initial value is set to Integer.MIN_VALUE, As long as it doesn't equal Integer.MIN_VALUE, It means that the recursive process has been calculated 
                    dp[i][j][k] = Integer.MIN_VALUE;
                }
            }
        }
        return Math.max(0, p(matrix, m, n, 0, 0, 0, dp));
    }

    //  Define two little people , Both of them started from (0,0) Set out , To the lower right corner , Each person chooses a different next step at the same time , If two little people jump to the same position , Count only one .
    public static int p(int[][] matrix, int m, int n, int x1, int y1, int x2, int[][][] dp) {
    
        if (dp[x1][y1][x2] != Integer.MIN_VALUE) {
    
            //  It shows that this process has been calculated , Take a value directly from the cache 
            return dp[x1][y1][x2];
        }
        if (x1 == m - 1 && y1 == n - 1) {
    
            //  We have reached the bottom right corner 
            //  Implied conditions ： The other point must also reach the lower right corner 
            //  Get a portion of cherries 
            dp[x1][y1][x2] = matrix[x1][y1];
            return matrix[x1][y1];
        }

        int next = -1;
        //  Next , Next 
        if (x1 + 1 < m && x2 + 1 < m && matrix[x1 + 1][y1] != -1 && matrix[x2 + 1][getY2(x1, y1, x2)] != -1) {
    
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2 + 1, dp), next);
        }
        //  Next , Right 
        if (x1 + 1 < m && getY2(x1, y1, x2) + 1 < n && matrix[x1 + 1][y1] != -1 && matrix[x2][getY2(x1, y1, x2) + 1] != -1) {
    
            next = Math.max(p(matrix, m, n, x1 + 1, y1, x2, dp), next);
        }
        //  Right , Next 
        if (y1 + 1 < n && x2 + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2 + 1][getY2(x1, y1, x2)] != -1) {
    
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2 + 1, dp), next);
        }
        //  Right , Right 
        if (y1 + 1 < n && getY2(x1, y1, x2) + 1 < m && matrix[x1][y1 + 1] != -1 && matrix[x2][getY2(x1, y1, x2) + 1] != -1) {
    
            next = Math.max(p(matrix, m, n, x1, y1 + 1, x2, dp), next);
        }
        if (next == -1) {
    
            dp[x1][y1][x2] = -1;
            return -1;
        }
        if (x1 == x2) {
    
            //  Arrive at the same location , Take only one value 
            //  Store the answer in the cache 
            dp[x1][y1][x2] = next + matrix[x1][y1];
            return dp[x1][y1][x2];
        }
        //  Store the answer in the cache 
        dp[x1][y1][x2] = next + matrix[x1][y1] + matrix[x2][getY2(x1, y1, x2)];
        return dp[x1][y1][x2];
    }

    public static int getY2(int x1, int y1, int x2) {
    
        return x1 + y1 - x2;
    }

Time complexity O(m*n*m),LeetCode In the direct AC.

more

Algorithm and data structure notes