【Leetcode】741. Cherry Pickup

题目地址：

https://leetcode.com/problems/cherry-pickup/

给定一个正方形矩阵，里面的数都是 0 0 0、 1 1 1或者 − 1 -1 −1， 1 1 1代表有樱桃， 0 0 0代表空地，可以走过去， − 1 -1 −1代表障碍物，不能走过去。现在要求从 ( 0 , 0 ) (0,0) (0,0)出发，每次只能向右或者向下走，走到 ( n − 1 , n − 1 ) (n-1,n-1) (n−1,n−1)，沿途不可以走到障碍物上，但可以走到空地和樱桃上，如果走到樱桃上则可以采摘，采完后樱桃就被采完了，接着再从 ( n − 1 , n − 1 ) (n-1,n-1) (n−1,n−1)一路返回 ( 0 , 0 ) (0,0) (0,0)，只能向左或者向上走，沿途也可以采摘樱桃，并且不能穿过障碍物。问两趟走完，最多能采多少樱桃。如果无法到达，则返回 0 0 0。

主要思路是动态规划。由于同一个樱桃不能采摘多次，所以我们在设计状态的时候，需要将这个情况考虑进去。至于走两趟这个问题，我们可以将返回的那一趟逆置一下，也变成从 ( 0 , 0 ) (0,0) (0,0)出发的一个路径即可。这样就相当于从 ( 0 , 0 ) (0,0) (0,0)出发走两趟，或者相当于两个人同时走。结果是等价的。

设方格矩阵为 g [ i ] [ j ] g[i][j] g[i][j]。接下来，设 f [ k ] [ i 1 ] [ i 2 ] f[k][i_1][i_2] f[k][i1​][i2​]表示从 ( 0 , 0 ) (0,0) (0,0)出发，第一个人走到 ( i 1 , k − i 1 ) (i_1,k-i_1) (i1​,k−i1​)，第二个人走到 ( i 2 , k − i 2 ) (i_2,k-i_2) (i2​,k−i2​)时，采摘的樱桃最大数。我们用 − 1 -1 −1来表示走不到那个格子。那么这个采摘樱桃的数量，可能有四种情况：

1、第一个人向右走到 ( i 1 , k − i 1 ) (i_1,k-i_1) (i1​,k−i1​)，第二个人也向右走到 ( i 2 , k − i 2 ) (i_2,k-i_2) (i2​,k−i2​)（即”右右“），这种情况下采摘的樱桃数为，如果 i 1 ≠ i 2 i_1\ne i_2 i1​​=i2​，那么 f [ k − 1 ] [ i 1 ] [ i 2 ] + g [ i 1 ] [ k − i 1 ] + g [ i 2 ] [ k − i 2 ] f[k-1][i_1][i_2]+g[i_1][k-i_1]+g[i_2][k-i_2] f[k−1][i1​][i2​]+g[i1​][k−i1​]+g[i2​][k−i2​]，否则 f [ k − 1 ] [ i 1 ] [ i 2 ] + g [ i 1 ] [ k − i 1 ] f[k-1][i_1][i_2]+g[i_1][k-i_1] f[k−1][i1​][i2​]+g[i1​][k−i1​]，这样就表达了“同一个樱桃不能采摘多次”这个意思。

2、第一个人向下走到 ( i 1 , k − i 1 ) (i_1,k-i_1) (i1​,k−i1​)，第二个人也向右走到 ( i 2 , k − i 2 ) (i_2,k-i_2) (i2​,k−i2​)（即”下右“），这种情况下采摘的樱桃数为，如果 i 1 ≠ i 2 i_1\ne i_2 i1​​=i2​，那么 f [ k − 1 ] [ i 1 − 1 ] [ i 2 ] + g [ i 1 ] [ k − i 1 ] + g [ i 2 ] [ k − i 2 ] f[k-1][i_1-1][i_2]+g[i_1][k-i_1]+g[i_2][k-i_2] f[k−1][i1​−1][i2​]+g[i1​][k−i1​]+g[i2​][k−i2​]，否则 f [ k − 1 ] [ i 1 − 1 ] [ i 2 ] + g [ i 1 ] [ k − i 1 ] f[k-1][i_1-1][i_2]+g[i_1][k-i_1] f[k−1][i1​−1][i2​]+g[i1​][k−i1​]。

…以此类推。这样一路递推下去，最后 f [ 2 n − 2 ] [ n − 1 ] [ n − 1 ] f[2n-2][n-1][n-1] f[2n−2][n−1][n−1]即为所求结果。但是，还有几个细节需要处理：

第一，如果 g [ i ] [ j ] = − 1 g[i][j]=-1 g[i][j]=−1，那么这个格子不允许走，需要特殊处理。如果其中一个人走到了障碍物，可以直接标记 f = − 1 f=-1 f=−1。

第二，如果在第 k k k层的某方格上，其上一层 f [ k − 1 ] f[k-1] f[k−1]的这个方格和这个方格的左边、上边和左上都是 − 1 -1 −1，其实说明了这个方格事实上是走不到的，也要直接标记为 − 1 -1 −1。

代码如下：

import java.util.Arrays;

public class Solution {
    public int cherryPickup(int[][] grid) {
    	// 特判
        if (grid == null || grid.length == 0 || grid[0].length == 0 || grid[0][0] == -1) {
            return 0;
        }
        
        int n = grid.length;
        int[][][] dp = new int[2 * n - 1][n][n];
    	
    	// 先将所有格子初始化为-1
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        // 初始化为左上那个格子，因为此时两个人的路径完全重合（都走到了(0,0)这一格）
        dp[0][0][0] = grid[0][0];
    
        for (int k = 1; k < 2 * n - 1; k++) {
            for (int i1 = 0; i1 < n; i1++) {
                for (int i2 = 0; i2 < n; i2++) {
                    // 算出来第一、二个人走到位置的纵坐标
                    int j1 = k - i1, j2 = k - i2;
                    // 如果纵坐标是合法的，就更新
                    if (j1 >= 0 && j1 < n && j2 >= 0 && j2 < n) {
                    	// 第一个人或第二个人走到了障碍物，直接标记为-1
                        if (grid[i1][j1] == -1 || grid[i2][j2] == -1) {
                            dp[k][i1][i2] = -1;
                            continue;
                        }
    					// 否则开始分四种情况，右右，下右，右下，下下分别更新
                        dp[k][i1][i2] = Math.max(dp[k][i1][i2], dp[k - 1][i1][i2]);
    
                        if (i1 > 0) {
                            dp[k][i1][i2] = Math.max(dp[k][i1][i2], dp[k - 1][i1 - 1][i2]);
                        }
    
                        if (i2 > 0) {
                            dp[k][i1][i2] = Math.max(dp[k][i1][i2], dp[k - 1][i1][i2 - 1]);
                        }
    
                        if (i1 > 0 && i2 > 0) {
                            dp[k][i1][i2] = Math.max(dp[k][i1][i2], dp[k - 1][i1 - 1][i2 - 1]);
                        }
    					// 如果更新完之后发现是-1，说明当前这个格子根本不能走到，则直接标记为-1
                        if (dp[k][i1][i2] == -1) {
                            continue;
                        }
                        // 否则说明当前格子是能走到的，此时看一下两个人是否走到了相同的格子，如果是，只加一次，否则加两次
                        dp[k][i1][i2] += grid[i1][j1];
                        if (i1 != i2) {
                            dp[k][i1][i2] += grid[i2][j2];
                        }
                    }
                }
            }
            
        }
        // 如果能走到，则返回，否则返回0
        return dp[2 * n - 2][n - 1][n - 1] == -1 ? 0 : dp[2 * n - 2][n - 1][n - 1];
    }
}
           

时空复杂度 O ( n 3 ) O(n^3) O(n3)。算法正确性可由数学归纳法得。