☕ DSA Java Articles

Topics › Dynamic Programming › 2D/3D DP and DP on Grids

Ninja and his Friends

Medium TUF ID 769 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A grid of r rows and c columns holds chocolates: grid[i][j] is the number in cell (i, j). Two friends, Alice and Bob, start on the top row: Alice at (0, 0) and Bob at (0, c - 1). Every second both of them move one row down at the same time, and each may go to the column on the left, the same column, or the column on the right: from (i, j) to (i + 1, j - 1), (i + 1, j) or (i + 1, j + 1). Nobody may leave the grid. Each friend collects every chocolate in every cell they stand on, including the start. If both stand on the same cell at the same moment, its chocolates are collected only once. Return the maximum total the two can collect once both reach the last row.

This is LeetCode 1463, Cherry Pickup II. Constraints: 2 ≤ r, c ≤ 70 and 0 ≤ grid[i][j] ≤ 100. The Java methods also accept a single row or a single column.

Example 1

grid = [[2, 3, 1, 2],
        [3, 4, 2, 2],
        [5, 6, 3, 5]]
answer = 21     // Alice 2 -> 4 -> 6 = 12, Bob 2 -> 2 -> 5 = 9

Example 2

grid = [[1, 1],
        [9, 1],
        [1, 1]]
answer = 14     // one friend takes the 9, the other the 1 beside it; meeting on the 9 would count it once

Why one walker at a time does not work

The tempting plan is to find Alice’s best path, remove its chocolates, then find Bob’s best path on what is left. Take grid = [[0, 1, 4], [2, 1, 0], [1, 1, 3]]. Alice’s best solo route is 0 -> 1 -> 3 (4 chocolates), but it grabs the 3 in the corner that only Bob could otherwise use. Bob is left with 4 -> 0 -> 1 = 5, a total of 9. Planned together, Alice goes 0 -> 2 -> 1 and Bob goes 4 -> 1 -> 3, for 11. The friends compete for the same cells, so their choices must be made together.

The key observation is that both move down exactly one row per step. After k steps both are on row k. So a single row index i describes where both are vertically, and the full state is (i, j1, j2): the shared row plus each friend’s column. Each step offers 3 × 3 = 9 combined moves. This is the 3D version of the grid DP: the earlier problems had (i, j), this one has one extra column.

The starting cells are fixed and the end cells are free (any cell of the last row), so the recursion is written from the start, going down, with the last row as the base case.

Approach 1: Recursion

Intuition. Let f(i, j1, j2) be the most chocolates the two can collect from row i to the bottom, given that Alice stands at column j1 and Bob at column j2 on row i. The cells they stand on now are worth grid[i][j1] + grid[i][j2], or just grid[i][j1] when j1 == j2. After that, they pick one of the 9 move pairs, and whichever they pick, the rest should be the best continuation from there. So

f(i, j1, j2) = -infinity                        if j1 or j2 is outside [0, c - 1]
f(r - 1, j1, j2) = value of the current cells
f(i, j1, j2) = value of the current cells + max over d1, d2 in {-1, 0, 1} of f(i + 1, j1 + d1, j2 + d2)
answer = f(0, 0, c - 1)

An out-of-grid column returns a very negative number, so the max never chooses it. The pair d1 = d2 = 0 is always legal from a legal state, so the maximum is always a real total.

The shared-cell rule is handled entirely by here: we never add a cell twice, and the recursion is free to let the friends meet when that really is best.

Algorithm.

  1. If either column is outside the grid, return NEG.
  2. Compute here, the chocolates on the current cells, counting a shared cell once.
  3. On the last row, return here.
  4. Otherwise try all 9 (d1, d2) pairs and return here plus the best result.
static int recursive(int[][] grid) {
    return solve(0, 0, grid[0].length - 1, grid);
}

static int solve(int i, int j1, int j2, int[][] grid) {
    int c = grid[0].length;
    if (j1 < 0 || j1 >= c || j2 < 0 || j2 >= c) return NEG;    // walked off the grid
    int here = (j1 == j2) ? grid[i][j1] : grid[i][j1] + grid[i][j2];
    if (i == grid.length - 1) return here;                       // last row: nothing below
    int best = NEG;
    for (int d1 = -1; d1 <= 1; d1++) {
        for (int d2 = -1; d2 <= 1; d2++) {
            best = Math.max(best, solve(i + 1, j1 + d1, j2 + d2, grid));
        }
    }
    return here + best;
}

NEG is -10^9 rather than Integer.MIN_VALUE. It is never actually added to anything here, but a sentinel that is far below any real answer without being at the edge of the int range stays safe if the code is later changed to add before comparing.

Complexity. Time O(9^r): every call spawns 9 calls for each of the r - 1 levels. Space O(r) for the recursion depth.

Approach 2: Memoization

Intuition. Different move sequences lead to the same (i, j1, j2). For example Alice going right then left and Alice going left then right both end in the same column. There are only r × c × c distinct states, so each answer should be computed once and cached.

Chocolate counts are non-negative, so every real answer is ≥ 0 and -1 is a safe “not computed” marker.

Algorithm.

  1. Create dp[r][c][c] filled with -1.
  2. Same recursion as before, but return dp[i][j1][j2] if it is known, and store each result before returning it.
static int memoization(int[][] grid) {
    int r = grid.length, c = grid[0].length;
    int[][][] dp = new int[r][c][c];
    for (int[][] plane : dp) for (int[] row : plane) Arrays.fill(row, -1);   // totals are >= 0, so -1 = unknown
    return memo(0, 0, c - 1, grid, dp);
}

static int memo(int i, int j1, int j2, int[][] grid, int[][][] dp) {
    int c = grid[0].length;
    if (j1 < 0 || j1 >= c || j2 < 0 || j2 >= c) return NEG;
    if (dp[i][j1][j2] != -1) return dp[i][j1][j2];
    int here = (j1 == j2) ? grid[i][j1] : grid[i][j1] + grid[i][j2];
    if (i == grid.length - 1) return dp[i][j1][j2] = here;
    int best = NEG;
    for (int d1 = -1; d1 <= 1; d1++) {
        for (int d2 = -1; d2 <= 1; d2++) {
            best = Math.max(best, memo(i + 1, j1 + d1, j2 + d2, grid, dp));
        }
    }
    return dp[i][j1][j2] = here + best;
}

Complexity. Time O(9 · r · c^2): each state is solved once with 9 lookups. Space O(r · c^2) for the table plus O(r) stack. For a 70 × 70 grid that is about 343,000 states.

Approach 3: Tabulation

Intuition. f(i, ·, ·) depends only on row i + 1, so fill the table from the last row upward. The base case is the whole last layer: for every pair of columns, the value of standing there. We compute every (j1, j2) pair on every row, even pairs the friends could never reach from the start. That is harmless: such entries mean “best total if they were standing here”, and the final answer reads only dp[0][0][c - 1].

In the bottom-up direction, out-of-grid neighbours are skipped with a bounds check rather than returned as NEG.

Algorithm.

  1. For every j1, j2: dp[r - 1][j1][j2] = value of the last-row cells.
  2. For i from r - 2 down to 0, for every j1, j2: take the best dp[i + 1][j1 + d1][j2 + d2] over the in-grid move pairs, and add the current cells’ value.
  3. Return dp[0][0][c - 1].
static int tabulation(int[][] grid) {
    int r = grid.length, c = grid[0].length;
    int[][][] dp = new int[r][c][c];
    for (int j1 = 0; j1 < c; j1++) {
        for (int j2 = 0; j2 < c; j2++) {
            dp[r - 1][j1][j2] = (j1 == j2) ? grid[r - 1][j1] : grid[r - 1][j1] + grid[r - 1][j2];
        }
    }
    for (int i = r - 2; i >= 0; i--) {
        for (int j1 = 0; j1 < c; j1++) {
            for (int j2 = 0; j2 < c; j2++) {
                int best = NEG;
                for (int d1 = -1; d1 <= 1; d1++) {
                    for (int d2 = -1; d2 <= 1; d2++) {
                        int n1 = j1 + d1, n2 = j2 + d2;
                        if (n1 >= 0 && n1 < c && n2 >= 0 && n2 < c) best = Math.max(best, dp[i + 1][n1][n2]);
                    }
                }
                int here = (j1 == j2) ? grid[i][j1] : grid[i][j1] + grid[i][j2];
                dp[i][j1][j2] = here + best;
            }
        }
    }
    return dp[0][0][c - 1];
}

Complexity. Time O(9 · r · c^2), space O(r · c^2).

Approach 4: Space optimized

Intuition. Layer i reads only layer i + 1. Keep one c × c array below for the row underneath, build the current layer in a fresh cur, then swap. Unlike the 1D grid problems, an in-place update is not safe: computing cur[j1][j2] reads up to nine neighbours of below, and some of them would already be overwritten. Two separate layers avoid that.

Algorithm.

  1. Fill below with the last-row values.
  2. For each row from r - 2 up to 0, compute cur from below exactly as in the tabulation, then set below = cur.
  3. Return below[0][c - 1].
static int spaceOptimized(int[][] grid) {
    int r = grid.length, c = grid[0].length;
    int[][] below = new int[c][c];
    for (int j1 = 0; j1 < c; j1++) {
        for (int j2 = 0; j2 < c; j2++) {
            below[j1][j2] = (j1 == j2) ? grid[r - 1][j1] : grid[r - 1][j1] + grid[r - 1][j2];
        }
    }
    for (int i = r - 2; i >= 0; i--) {
        int[][] cur = new int[c][c];
        for (int j1 = 0; j1 < c; j1++) {
            for (int j2 = 0; j2 < c; j2++) {
                int best = NEG;
                for (int d1 = -1; d1 <= 1; d1++) {
                    for (int d2 = -1; d2 <= 1; d2++) {
                        int n1 = j1 + d1, n2 = j2 + d2;
                        if (n1 >= 0 && n1 < c && n2 >= 0 && n2 < c) best = Math.max(best, below[n1][n2]);
                    }
                }
                int here = (j1 == j2) ? grid[i][j1] : grid[i][j1] + grid[i][j2];
                cur[j1][j2] = here + best;
            }
        }
        below = cur;
    }
    return below[0][c - 1];
}

Dry run of the winning route on Example 1:

row Alice column Bob column collected this row running total
0 0 3 2 + 2 4
1 1 3 4 + 2 10
2 1 3 6 + 5 21

The table value dp[0][0][3] equals 21, and this is one route that achieves it.

Complexity. Time O(9 · r · c^2), space O(c^2).

Edge cases and pitfalls