LeetCode 741. 摘樱桃

Categories:

题目描述
思路分析
1. 解法一：三维动态规划（推荐）
相似题目

题目描述

✅ 741. 摘樱桃

思路分析

解法一：三维动态规划（推荐）

核心思路：

将”去程 + 回程摘最多樱桃”转化为”两个人同时从起点走到终点”的等价模型

设 dp[t][r1][r2] 表示走了 t 步时，两人分别在第 r1 行和第 r2 行，所能摘到的最多樱桃数

两人列坐标可由 c1 = t - r1、c2 = t - r2 推导，无需单独存储

若两人处于同一格，只计一次；若某格为 -1（荆棘），则该状态不可达

每步从上一时刻的合法状态转移而来，枚举两人各自的来向（上/左）

复杂度分析：

时间复杂度：O(n³)，其中 n 表示网格边长，三重循环枚举步数 t 和两人行坐标

空间复杂度：O(n²)，滚动数组压缩步数维度

class Solution {
  public int cherryPickup(int[][] grid) {
    int n = grid.length;
    // dp[r1][r2] 表示当前步两人分别在 r1、r2 行时的最大樱桃数
    int[][] dp = new int[n][n];
    for (int[] row : dp) {
      Arrays.fill(row, Integer.MIN_VALUE);
    }
    dp[0][0] = grid[0][0];

    for (int t = 1; t <= 2 * (n - 1); t++) {
      int[][] ndp = new int[n][n];
      for (int[] row : ndp) {
        Arrays.fill(row, Integer.MIN_VALUE);
      }

      // 枚举两人的行坐标
      for (int r1 = Math.max(0, t - (n - 1)); r1 <= Math.min(t, n - 1); r1++) {
        for (int r2 = r1; r2 <= Math.min(t, n - 1); r2++) {
          int c1 = t - r1;
          int c2 = t - r2;

          // 列坐标越界或遇到荆棘则跳过
          if (c1 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {
            continue;
          }

          // 统计当前格子的樱桃，若两人重合只加一次
          int cherries = grid[r1][c1];
          if (r1 != r2) {
            cherries += grid[r2][c2];
          }

          // 枚举上一步两人的来向：向下（行-1）或向右（列-1，即行不变）
          int best = Integer.MIN_VALUE;
          for (int dr1 : new int[]{0, 1}) {
            for (int dr2 : new int[]{0, 1}) {
              int pr1 = r1 - dr1;
              int pr2 = r2 - dr2;
              if (pr1 >= 0 && pr2 >= 0 && dp[pr1][pr2] != Integer.MIN_VALUE) {
                best = Math.max(best, dp[pr1][pr2]);
              }
            }
          }

          if (best != Integer.MIN_VALUE) {
            ndp[r1][r2] = Math.max(ndp[r1][r2], best + cherries);
          }
        }
      }
      dp = ndp;
    }

    return Math.max(0, dp[n - 1][n - 1]);
  }
}

func cherryPickup(grid [][]int) int {
    n := len(grid)
    const minVal = math.MinInt32

    // dp[r1][r2] 表示两人分别在 r1、r2 行时的最大樱桃数
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = minVal
        }
    }
    dp[0][0] = grid[0][0]

    for t := 1; t <= 2*(n-1); t++ {
        ndp := make([][]int, n)
        for i := range ndp {
            ndp[i] = make([]int, n)
            for j := range ndp[i] {
                ndp[i][j] = minVal
            }
        }

        rMin := max741(0, t-(n-1))
        rMax := min741(t, n-1)

        for r1 := rMin; r1 <= rMax; r1++ {
            for r2 := r1; r2 <= rMax; r2++ {
                c1 := t - r1
                c2 := t - r2

                // 列越界或荆棘则跳过
                if c1 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1 {
                    continue
                }

                cherries := grid[r1][c1]
                if r1 != r2 {
                    cherries += grid[r2][c2]
                }

                // 枚举上一步的来向
                best := minVal
                for _, dr1 := range []int{0, 1} {
                    for _, dr2 := range []int{0, 1} {
                        pr1, pr2 := r1-dr1, r2-dr2
                        if pr1 >= 0 && pr2 >= 0 && dp[pr1][pr2] != minVal {
                            if dp[pr1][pr2] > best {
                                best = dp[pr1][pr2]
                            }
                        }
                    }
                }

                if best != minVal && best+cherries > ndp[r1][r2] {
                    ndp[r1][r2] = best + cherries
                }
            }
        }
        dp = ndp
    }

    if dp[n-1][n-1] < 0 {
        return 0
    }
    return dp[n-1][n-1]
}

func max741(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min741(a, b int) int {
    if a < b {
        return a
    }
    return b
}

相似题目

题目	难度	考察点
64. 最小路径和	中等	动态规划
174. 地下城游戏	困难	动态规划
931. 下降路径最小和	中等	动态规划
1463. 摘樱桃 II	困难	三维DP
329. 矩阵中的最长递增路径	困难	记忆化搜索
120. 三角形最小路径和	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/95731090