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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
/**
 * Find the maximum number of cherries that can be collected.
 * Dynamic Programming (3D) approach.
 *
 * @param {number[][]} grid - Grid representing a field of cherries
 * @return {number} - Maximum number of cherries
 */
function cherryPickup(grid) {
  const n = grid.length;
 
  // Initialize 3D DP array
  const dp = Array(n).fill().map(() =>
    Array(n).fill().map(() =>
      Array(n).fill(-Infinity)
    )
  );
 
  // Base case
  if (grid[0][0] !== -1) {
    dp[0][0][0] = grid[0][0];
  } else {
    return 0;  // If starting cell is a thorn, no cherries can be collected
  }
 
  // Fill DP array
  for (let r1 = 0; r1 < n; r1++) {
    for (let c1 = 0; c1 < n; c1++) {
      for (let r2 = 0; r2 < n; r2++) {
        // Calculate c2
        const c2 = r1 + c1 - r2;
 
        // Skip invalid cells
        if (c2 < 0 || c2 >= n || grid[r1][c1] === -1 || grid[r2][c2] === -1) {
          continue;
        }
 
        // Calculate cherries collected
        let cherries = grid[r1][c1];
        if (r1 !== r2 || c1 !== c2) {
          cherries += grid[r2][c2];
        }
 
        // Calculate maximum cherries from previous positions
        let prev = -Infinity;
 
        // Both move down
        if (r1 > 0 && r2 > 0) {
          prev = Math.max(prev, dp[r1 - 1][c1][r2 - 1]);
        }
 
        // Person 1 moves down, person 2 moves right
        if (r1 > 0 && c2 > 0) {
          prev = Math.max(prev, dp[r1 - 1][c1][r2]);
        }
 
        // Person 1 moves right, person 2 moves down
        if (c1 > 0 && r2 > 0) {
          prev = Math.max(prev, dp[r1][c1 - 1][r2 - 1]);
        }
 
        // Both move right
        if (c1 > 0 && c2 > 0) {
          prev = Math.max(prev, dp[r1][c1 - 1][r2]);
        }
 
        // Update DP array
        if (prev !== -Infinity) {
          dp[r1][c1][r2] = cherries + prev;
        }
      }
    }
  }
 
  return Math.max(0, dp[n - 1][n - 1][n - 1]);
}
 
/**
 * Find the maximum number of cherries that can be collected.
 * Dynamic Programming with Memoization approach.
 *
 * @param {number[][]} grid - Grid representing a field of cherries
 * @return {number} - Maximum number of cherries
 */
function cherryPickupMemoization(grid) {
  const n = grid.length;
 
  // Initialize memoization table
  const memo = Array(n).fill().map(() =>
    Array(n).fill().map(() =>
      Array(n).fill(-1)
    )
  );
 
  // Define recursive function
  function dp(r1, c1, r2) {
    // Calculate c2
    const c2 = r1 + c1 - r2;
 
    // Check if position is valid
    if (r1 < 0 || c1 < 0 || r2 < 0 || c2 < 0 || r1 >= n || c1 >= n || r2 >= n || c2 >= n) {
      return -Infinity;
    }
 
    // Check if position contains a thorn
    if (grid[r1][c1] === -1 || grid[r2][c2] === -1) {
      return -Infinity;
    }
 
    // Base case: starting position
    if (r1 === 0 && c1 === 0 && r2 === 0) {
      return grid[0][0];
    }
 
    // Check if already computed
    if (memo[r1][c1][r2] !== -1) {
      return memo[r1][c1][r2];
    }
 
    // Calculate cherries collected
    let cherries = grid[r1][c1];
    if (r1 !== r2 || c1 !== c2) {
      cherries += grid[r2][c2];
    }
 
    // Calculate maximum cherries from previous positions
    const prev = Math.max(
      dp(r1 - 1, c1, r2 - 1),  // Both move down
      dp(r1 - 1, c1, r2),      // Person 1 moves down, person 2 moves right
      dp(r1, c1 - 1, r2 - 1),  // Person 1 moves right, person 2 moves down
      dp(r1, c1 - 1, r2)       // Both move right
    );
 
    // Update memoization table
    memo[r1][c1][r2] = cherries + prev;
    return memo[r1][c1][r2];
  }
 
  const result = dp(n - 1, n - 1, n - 1);
  return Math.max(0, result);
}
 
/**
 * Find the maximum number of cherries that can be collected.
 * Optimized Dynamic Programming with Memoization approach.
 *
 * @param {number[][]} grid - Grid representing a field of cherries
 * @return {number} - Maximum number of cherries
 */
function cherryPickupOptimized(grid) {
  const n = grid.length;
 
  // If starting cell is a thorn, no cherries can be collected
  if (grid[0][0] === -1) {
    return 0;
  }
 
  // Initialize memoization table
  const memo = new Map();
 
  // Define recursive function
  function dp(r1, c1, r2) {
    // Calculate c2
    const c2 = r1 + c1 - r2;
 
    // Check if position is valid
    if (r1 < 0 || c1 < 0 || r2 < 0 || c2 < 0 || r1 >= n || c1 >= n || r2 >= n || c2 >= n) {
      return -Infinity;
    }
 
    // Check if position contains a thorn
    if (grid[r1][c1] === -1 || grid[r2][c2] === -1) {
      return -Infinity;
    }
 
    // Base case: destination reached
    if (r1 === n - 1 && c1 === n - 1) {
      return grid[r1][c1];
    }
 
    // Create a unique key for the memo map
    const key = `${r1},${c1},${r2}`;
 
    // Check if already computed
    if (memo.has(key)) {
      return memo.get(key);
    }
 
    // Calculate cherries collected
    let cherries = grid[r1][c1];
    if (r1 !== r2 || c1 !== c2) {
      cherries += grid[r2][c2];
    }
 
    // Calculate maximum cherries from next positions
    const next = Math.max(
      dp(r1 + 1, c1, r2 + 1),  // Both move down
      dp(r1 + 1, c1, r2),      // Person 1 moves down, person 2 moves right
      dp(r1, c1 + 1, r2 + 1),  // Person 1 moves right, person 2 moves down
      dp(r1, c1 + 1, r2)       // Both move right
    );
 
    // Update memoization table
    const result = cherries + (next === -Infinity ? -Infinity : next);
    memo.set(key, result);
    return result;
  }
 
  const result = dp(0, 0, 0);
  return Math.max(0, result);
}
 
// Test cases
const grid1 = [
  [0, 1, -1],
  [1, 0, -1],
  [1, 1, 1]
];
console.log(cherryPickup(grid1));  // 5
console.log(cherryPickupMemoization(grid1));  // 5
console.log(cherryPickupOptimized(grid1));  // 5
 
const grid2 = [
  [1, 1, -1],
  [1, -1, 1],
  [-1, 1, 1]
];
console.log(cherryPickup(grid2));  // 0
console.log(cherryPickupMemoization(grid2));  // 0
console.log(cherryPickupOptimized(grid2));  // 0