43:23
DP 13. Cherry Pickup II | 3D DP Made Easy | DP On Grids
take U forward
Overview
This video explains how to solve the Cherry Pickup II problem using dynamic programming, specifically focusing on a 3D DP approach. The problem involves two agents, Alice and Bob, starting at the top row of a grid and moving to the bottom row, collecting cherries. The key challenge is to maximize the total cherries collected while handling the constraint that if both agents land on the same cell, the cherries are counted only once. The video covers the recursive solution, memoization, tabulation, and space optimization techniques for this problem, emphasizing the importance of considering both agents' movements simultaneously to correctly manage shared cells.
How was this?
Save this permanently with flashcards, quizzes, and AI chat
Chapters
- The problem involves two agents (Alice and Bob) collecting cherries from an R x C grid, starting at (0, 0) and (0, C-1) respectively.
- Both agents move simultaneously downwards, with three possible moves: down-left, down, or down-right.
- Cherries in a cell are collected when an agent visits it; if both visit the same cell, cherries are collected only once.
- The goal is to maximize the total cherries collected by both agents by the time they reach the last row.
- Greedy approaches do not work because an locally optimal choice might prevent a globally optimal solution due to the non-uniform distribution of cherries and the shared cell constraint.
Understanding the problem constraints and why simple greedy strategies fail is crucial for recognizing the need for a more sophisticated approach like dynamic programming.
An example grid is shown where Alice and Bob take different paths, and the total cherries collected (21) is calculated, highlighting the potential for different path combinations.
- Since both agents move simultaneously and their paths can overlap, their states must be considered together.
- The state can be defined by the current row `i` (common for both) and the columns `j1` for Alice and `j2` for Bob.
- The recursive function `solve(i, j1, j2)` returns the maximum cherries from row `i` onwards, given Alice is at `j1` and Bob is at `j2`.
- Base cases include out-of-bounds conditions (returning a very small negative number to avoid selection) and reaching the last row (calculating cherries based on whether `j1 == j2`).
- The transitions involve exploring all 9 possible combined moves for Alice and Bob from row `i` to `i+1`.
Defining the correct state and transitions is the foundation of any DP solution. This step breaks down the complex problem into manageable subproblems.
The 9 possible moves are visualized: Alice moves left, center, or right, and for each of Alice's moves, Bob also has 3 independent moves, creating 3x3=9 combinations.
- The recursive solution has overlapping subproblems, leading to exponential time complexity.
- Memoization is applied by storing the results of `solve(i, j1, j2)` in a 3D DP table (e.g., `dp[i][j1][j2]`).
- Before computing a state, the DP table is checked; if the value exists (is not -1), it's returned directly.
- The DP table dimensions are `R x C x C`, representing the number of possible states.
- Memoization reduces the time complexity from exponential to O(R * C * C * 9) due to the 9 transitions per state.
Memoization transforms an inefficient recursive solution into a polynomial-time solution by avoiding redundant computations, making it feasible for larger grids.
A 3D vector `dp[R][C][C]` is initialized with -1. When `solve(i, j1, j2)` is called, it first checks `dp[i][j1][j2]`. If it's not -1, the stored value is returned; otherwise, the computation proceeds, and the result is stored before returning.
- Tabulation builds the solution bottom-up, starting from the base cases.
- The DP table `dp[R][C][C]` is filled iteratively, usually starting from the last row and moving upwards.
- The base cases are handled by initializing the last row of the DP table (`dp[R-1][j1][j2]`) based on the cherries collected at that row.
- Nested loops iterate through rows (from R-2 down to 0), Alice's column (`j1`), and Bob's column (`j2`).
- For each state `(i, j1, j2)`, the maximum value is calculated by considering the 9 possible next states `(i+1, next_j1, next_j2)` and adding the current cherries.
Tabulation provides an alternative, often more intuitive, way to implement DP without recursion, which can sometimes be more efficient in terms of stack usage.
The DP table `dp[R][C][C]` is filled. For `i = R-2` down to `0`, and for all `j1`, `j2`, `dp[i][j1][j2]` is computed by looking at `dp[i+1][...]` values and adding `grid[i][j1]` (and `grid[i][j2]` if `j1 != j2`).
- In tabulation, to compute row `i`, only values from row `i+1` are needed.
- This allows for space optimization from O(R * C * C) to O(C * C) by using only two 2D arrays: one for the current row (`current_dp`) and one for the next row (`front_dp`).
- After computing the `current_dp` for row `i`, it becomes the `front_dp` for the next iteration (row `i-1`).
- The base case initialization uses the `front_dp` array for the last row.
- The final answer is found in `front_dp[0][C-1]` after the loops complete.
Space optimization is crucial for problems with large dimensions, allowing solutions to fit within memory constraints while maintaining the same time complexity.
Two 2D vectors, `front` and `current`, both of size `C x C`, are used. `front` stores results for `i+1`, and `current` is computed for row `i`. After row `i` is processed, `front` is updated with `current`'s values.
Key takeaways
- Problems involving multiple agents moving simultaneously on a grid often require DP states that capture the positions of all agents.
- When agents can occupy the same cell, the DP state transition must account for this overlap to avoid double-counting.
- The number of possible moves from a state determines the multiplier in the time complexity (e.g., 9 combinations for two agents with 3 moves each).
- Memoization is a top-down DP approach that uses recursion with a cache to store results of overlapping subproblems.
- Tabulation is a bottom-up DP approach that iteratively fills a DP table starting from base cases.
- Space optimization in DP is possible when the computation for the current state only depends on a limited number of previous states (e.g., the immediately preceding row).
- When dealing with out-of-bounds conditions in DP, returning a very small negative number (or negative infinity) is often preferred over `INT_MIN` to prevent overflow when adding to other negative values.
Key terms
Dynamic Programming (DP)3D DP StateMemoizationTabulationSpace OptimizationOverlapping SubproblemsBase CasesTransitionsState Space
Test your understanding
- Why is it necessary to consider Alice and Bob's movements simultaneously rather than solving for each independently?
- How does the 3D DP state `(i, j1, j2)` capture all the necessary information to solve the subproblem?
- What are the base cases for the recursive solution to the Cherry Pickup II problem, and why are they important?
- How does memoization improve the time complexity of the recursive solution, and what is the resulting complexity?
- Explain the strategy for space optimization from a 3D DP table to a 2D DP approach.