Chocolates Pickup (Two Robots Problem)

Sandhiya Priya
2d
141
0
1

100

Article

Problem Summary

This is a classic 3D Dynamic Programming (DP) problem where two agents move simultaneously.

Two robots start from:

Robot 1 → (0, 0)
Robot 2 → (0, m-1)

They move row by row downward, and each step they can move:

left-down (j - 1)
down (j)
right-down (j + 1)

Goal:
Maximize total chocolates collected.

If both land on same cell → count only once.

Key Insight

At every row:

We only care about positions of both robots

So state becomes:

dp[row][col1][col2]

Meaning:
Maximum chocolates collected starting from row when:

Robot1 is at col1
Robot2 is at col2

Intuition

At each step:

Robot1 has 3 moves
Robot2 has 3 moves

Total transitions = 9 combinations

So:

O(n m m 9)
≈ O(n m²)

Important Trick

If:

col1 == col2

→ take grid[row][col1] only once

Else:

grid[row][col1] + grid[row][col2]

DP Transition

For each state:

dp[r][c1][c2] = grid[r][c1] + (c1 == c2 ? 0 : grid[r][c2]) + max(next moves)

Base Case

At last row:

dp[n-1][c1][c2] = value at last row

Java Solution (Bottom-Up DP)

class Solution {
    public int maxChocolate(int grid[][]) {
        int n = grid.length;
        int m = grid[0].length;

        int[][][] dp = new int[n][m][m];

        // initialize last row
        for (int c1 = 0; c1 < m; c1++) {
            for (int c2 = 0; c2 < m; c2++) {
                if (c1 == c2)
                    dp[n - 1][c1][c2] = grid[n - 1][c1];
                else
                    dp[n - 1][c1][c2] = grid[n - 1][c1] + grid[n - 1][c2];
            }
        }

        // fill DP from bottom to top
        for (int r = n - 2; r >= 0; r--) {
            for (int c1 = 0; c1 < m; c1++) {
                for (int c2 = 0; c2 < m; c2++) {

                    int best = 0;

                    for (int d1 = -1; d1 <= 1; d1++) {
                        for (int d2 = -1; d2 <= 1; d2++) {

                            int nc1 = c1 + d1;
                            int nc2 = c2 + d2;

                            if (nc1 >= 0 && nc1 < m && nc2 >= 0 && nc2 < m) {

                                int value = (c1 == c2)
                                        ? grid[r][c1]
                                        : grid[r][c1] + grid[r][c2];

                                value += dp[r + 1][nc1][nc2];

                                best = Math.max(best, value);
                            }
                        }
                    }

                    dp[r][c1][c2] = best;
                }
            }
        }

        return dp[0][0][m - 1];
    }
}

Complexity

Time Complexity: O(n × m² × 9) → O(n × m²)
Space Complexity: O(n × m²)

Key Takeaways

This is a 3D DP problem
Two agents → state becomes (row, col1, col2)
Every move has 9 combinations
Avoid double counting when positions overlap

Pattern Recognition

If you see:

two players / two robots
simultaneous movement
maximize/minimize sum

Think:

“Multi-agent DP (3D DP)”