Skip to content

3363. Find the Maximum Number of Fruits Collected 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
 public:
  int maxCollectedFruits(vector<vector<int>>& fruits) {
    return getTopLeft(fruits) + getTopRight(fruits) + getBottomLeft(fruits) -
           2 * fruits.back().back();
  }

 private:
  int getTopLeft(const vector<vector<int>>& fruits) {
    const int n = fruits.size();
    int res = 0;
    for (int i = 0; i < n; ++i)
      res += fruits[i][i];
    return res;
  }

  int getTopRight(const vector<vector<int>>& fruits) {
    const int n = fruits.size();
    // dp[i][j] := the number of fruits collected from (0, n - 1) to (i, j)
    vector<vector<int>> dp(n, vector<int>(n));
    dp[0][n - 1] = fruits[0][n - 1];
    for (int x = 0; x < n; ++x) {
      for (int y = 0; y < n; ++y) {
        if (x >= y && !(x == n - 1 && y == n - 1))
          continue;
        for (const auto& [dx, dy] :
             vector<pair<int, int>>{{1, -1}, {1, 0}, {1, 1}}) {
          const int i = x - dx;
          const int j = y - dy;
          if (i < 0 || i == n || j < 0 || j == n)
            continue;
          if (i < j && j < n - 1 - i)
            continue;
          dp[x][y] = max(dp[x][y], dp[i][j] + fruits[x][y]);
        }
      }
    }

    return dp[n - 1][n - 1];
  }

  int getBottomLeft(const vector<vector<int>>& fruits) {
    const int n = fruits.size();
    // dp[i][j] := the number of fruits collected from (n - 1, 0) to (i, j)
    vector<vector<int>> dp(n, vector<int>(n));
    dp[n - 1][0] = fruits[n - 1][0];
    for (int y = 0; y < n; ++y) {
      for (int x = 0; x < n; ++x) {
        if (x <= y && !(x == n - 1 && y == n - 1))
          continue;
        for (const auto& [dx, dy] :
             vector<pair<int, int>>{{-1, 1}, {0, 1}, {1, 1}}) {
          const int i = x - dx;
          const int j = y - dy;
          if (i < 0 || i == n || j < 0 || j == n)
            continue;
          if (j < i && i < n - 1 - j)
            continue;
          dp[x][y] = max(dp[x][y], dp[i][j] + fruits[x][y]);
        }
      }
    }
    return dp[n - 1][n - 1];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
  public int maxCollectedFruits(int[][] fruits) {
    final int n = fruits.length;
    return getTopLeft(fruits) + getTopRight(fruits) + getBottomLeft(fruits) //
        - 2 * fruits[n - 1][n - 1];
  }

  private int getTopLeft(int[][] fruits) {
    final int n = fruits.length;
    int res = 0;
    for (int i = 0; i < n; ++i)
      res += fruits[i][i];
    return res;
  }

  private int getTopRight(int[][] fruits) {
    final int n = fruits.length;
    // dp[i][j] := the number of fruits collected from (0, n - 1) to (i, j)
    int[][] dp = new int[n][n];
    dp[0][n - 1] = fruits[0][n - 1];
    for (int x = 0; x < n; ++x)
      for (int y = 0; y < n; ++y) {
        if (x >= y && !(x == n - 1 && y == n - 1))
          continue;
        for (int[] dir : new int[][] {{1, -1}, {1, 0}, {1, 1}}) {
          final int i = x - dir[0];
          final int j = y - dir[1];
          if (i < 0 || i == n || j < 0 || j == n)
            continue;
          if (i < j && j < n - 1 - i)
            continue;
          dp[x][y] = Math.max(dp[x][y], dp[i][j] + fruits[x][y]);
        }
      }
    return dp[n - 1][n - 1];
  }

  private int getBottomLeft(int[][] fruits) {
    final int n = fruits.length;
    // dp[i][j] := the number of fruits collected from (n - 1, 0) to (i, j)
    int[][] dp = new int[n][n];
    dp[n - 1][0] = fruits[n - 1][0];
    for (int y = 0; y < n; ++y)
      for (int x = 0; x < n; ++x) {
        if (x <= y && !(x == n - 1 && y == n - 1))
          continue;
        for (int[] dir : new int[][] {{-1, 1}, {0, 1}, {1, 1}}) {
          final int i = x - dir[0];
          final int j = y - dir[1];
          if (i < 0 || i == n || j < 0 || j == n)
            continue;
          if (j < i && i < n - 1 - j)
            continue;
          dp[x][y] = Math.max(dp[x][y], dp[i][j] + fruits[x][y]);
        }
      }
    return dp[n - 1][n - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:
  def maxCollectedFruits(self, fruits: list[list[int]]) -> int:
    n = len(fruits)

    def getTopLeft() -> int:
      return sum(fruits[i][i] for i in range(n))

    def getTopRight() -> int:
      # dp[i][j] := the number of fruits collected from (0, n - 1) to (i, j)
      dp = [[0] * n for _ in range(n)]
      dp[0][-1] = fruits[0][-1]
      for x in range(n):
        for y in range(n):
          if x >= y and (x, y) != (n - 1, n - 1):
            continue
          for dx, dy in [(1, -1), (1, 0), (1, 1)]:
            i = x - dx
            j = y - dy
            if i < 0 or i == n or j < 0 or j == n:
              continue
            if i < j < n - 1 - i:
              continue
            dp[x][y] = max(dp[x][y], dp[i][j] + fruits[x][y])
      return dp[-1][-1]

    def getBottomLeft() -> int:
      # dp[i][j] := the number of fruits collected from (n - 1, 0) to (i, j)
      dp = [[0] * n for _ in range(n)]
      dp[-1][0] = fruits[-1][0]
      for y in range(n):
        for x in range(n):
          if x <= y and (x, y) != (n - 1, n - 1):
            continue
          for dx, dy in [(-1, 1), (0, 1), (1, 1)]:
            i = x - dx
            j = y - dy
            if i < 0 or i == n or j < 0 or j == n:
              continue
            if j < i < n - 1 - j:
              continue
            dp[x][y] = max(dp[x][y], dp[i][j] + fruits[x][y])
      return dp[-1][-1]

    return getTopLeft() + getTopRight() + getBottomLeft() - 2 * fruits[-1][-1]