741.摘樱桃

链接：741.摘樱桃
难度：Hard
标签：数组、动态规划、矩阵
简介：你的任务是在遵守下列规则的情况下，尽可能的摘到最多樱桃。

题解 1 - python

• 编辑时间：2024-05-07
• 执行用时：466ms
• 内存消耗：26.72MB
• 编程语言：python
• 解法介绍：dp[step][x1][x2]表示共走了step步后，第一个人往垂直方向走x1步，第二个人在垂直方向走x2步，此时能获得的最大樱桃数。

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        MAX_STEP = (n - 1) * 2 + 1
        dp = [[[-inf for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(MAX_STEP)]
        dp[0][0][0] = grid[0][0]
        for step in range(1, MAX_STEP):
            MAX_X = min(step, n - 1) + 1
            for x1 in range(MAX_X):
                y1 = step - x1
                if y1 < n:
                    for x2 in range(MAX_X):
                        y2 = step - x2
                        if y2 < n:
                            if grid[x1][y1] != -1 and grid[x2][y2] != -1:
                                dp[step][x1][x2] = max(
                                    dp[step - 1][x1][x2],
                                    dp[step - 1][x1 - 1][x2],
                                    dp[step - 1][x1][x2 - 1],
                                    dp[step - 1][x1 - 1][x2 - 1],
                                )
                                dp[step][x1][x2] += grid[x1][y1]
                                if x1 != x2 or y1 != y2: dp[step][x1][x2] += grid[x2][y2]
        res = 0
        for item in dp[MAX_STEP - 1]:
            res = max(res, max(item))
        return res

题解 2 - cpp

• 编辑时间：2022-07-11
• 执行用时：84ms
• 内存消耗：34.2MB
• 编程语言：cpp
• 解法介绍：问题转化为两个人从起点到终点路径中共有多少个樱桃,dp[i][j][k]表示总共 i 步的时候第一个人 x 在 j 第二个人 x 在 k,此时最大的樱桃数。

class Solution {
   public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size(), max_step = n * 2 - 1;
        vector<vector<vector<int>>> dp(
            max_step, vector<vector<int>>(n, vector<int>(n, INT_MIN)));
        dp[0][0][0] = grid[0][0];
        for (int step = 1; step < max_step; step++) {
            int minCell = max(step - n + 1, 0), maxCell = min(n - 1, step);
            for (
                // x1最少走0格,如果step已经超过n,那x1最少也得n格
                int x1 = minCell;
                //  x1最多走到第n-1格
                x1 <= maxCell; x1++) {
                int y1 = step - x1;
                if (grid[x1][y1] == -1) continue;
                for (int x2 = minCell; x2 <= maxCell; x2++) {
                    int y2 = step - x2;
                    if (grid[x2][y2] == -1) continue;
                    int cnt = dp[step - 1][x1][x2]; // 都向右走一步
                    if (x1) cnt = max(cnt, dp[step - 1][x1 - 1][x2]); // x1向下走一步
                    if (x2) cnt = max(cnt, dp[step - 1][x1][x2 - 1]); // x2向下走一步
                    if (x1 && x2) cnt = max(cnt, dp[step - 1][x1 - 1][x2 - 1]); // 都向下走一步
                    cnt += grid[x1][y1];
                    if (x1 != x2) cnt += grid[x2][y2];
                    dp[step][x1][x2] = cnt;
                }
            }
        }
        return max(0, dp[max_step - 1][n - 1][n - 1]);
    }
};