#3363
Find the Maximum Number of Fruits Collected
HardArrayDynamic ProgrammingMatrixDynamic ProgrammingMatrix Traversal
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n)Space O(n)
Use dynamic programming to calculate the maximum fruits collected by each child independently, then combine results. This avoids redundant calculations.
⚙️
Algorithm
3 steps- 1Step 1: Create a DP table for each child to track maximum fruits collected at each position.
- 2Step 2: Fill the DP table based on possible moves for each child.
- 3Step 3: Combine results from the DP tables to find the maximum fruits collected.
solution.py9 lines
1def maxFruits(fruits):
2 n = len(fruits)
3 dp1, dp2, dp3 = [[0]*n for _ in range(n)], [[0]*n for _ in range(n)], [[0]*n for _ in range(n)]
4 for i in range(n):
5 for j in range(n):
6 dp1[i][j] = fruits[i][j] + max(dp1[i-1][j] if i > 0 else 0, dp1[i][j-1] if j > 0 else 0)
7 dp2[i][j] = fruits[i][j] + max(dp2[i-1][j] if i > 0 else 0, dp2[i-1][j+1] if j < n-1 else 0)
8 dp3[i][j] = fruits[i][j] + max(dp3[i+1][j] if i < n-1 else 0, dp3[i][j+1] if j < n-1 else 0)
9 return max(dp1[n-1][n-1], dp2[n-1][n-1], dp3[n-1][n-1])ℹ
Complexity note: Dynamic programming reduces redundant calculations by storing intermediate results, leading to linear complexity.
- 1Children's paths do not intersect.
- 2Dynamic programming optimizes path calculations.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.