Pizza With 3n Slices: Circular DP Selection

You have a circular pizza cut into 3n slices of varying sizes. You and two friends take turns picking slices. In each round, you pick any remaining slice, then your two friends immediately take the two slices adjacent to it (one clockwise, one counterclockwise). After n rounds the pizza is gone. Your goal: maximize the total size of the slices you pick.

This is LeetCode 1388: Pizza With 3n Slices, and it is one of the best problems for learning how to extend the House Robber DP pattern to a harder constraint: selecting exactly k non-adjacent elements from a circular array.

Why this problem matters

At first glance, this looks like a greedy problem. Pick the largest slice, let your friends take the neighbors, repeat. But greedy fails here because taking a large slice might force you to lose access to an even better combination later. The problem requires optimization over dependent choices, which is the domain of dynamic programming.

The deeper insight is that "Pizza With 3n Slices" reduces to a well-known DP pattern. Once you see the reduction, the solution reuses building blocks from House Robber and House Robber II. This makes it a great example of how recognizing problem transformations turns hard problems into variations of ones you already know.

The key insight

The first step is a non-obvious reduction. It can be proven that picking any slice and having friends take the adjacent ones is equivalent to the following: from a circular array of 3n values, choose exactly n values such that no two chosen values are adjacent in the circle, and maximize their sum.

Once you have that, you are solving a constrained version of House Robber II. In House Robber II, you maximize the sum of non-adjacent elements in a circular array with no limit on how many you pick. Here, you must pick exactly n of them. The circular constraint is handled the same way: run the DP twice, once on slices[0..3n-2] (excluding the last) and once on slices[1..3n-1] (excluding the first), then take the maximum.

The DP itself uses two dimensions: dp[i][j] represents the maximum sum when considering the first i elements and picking exactly j of them, with no two adjacent. The transition is:

• Skip element i: dp[i][j] = dp[i-1][j]
• Pick element i: dp[i][j] = dp[i-2][j-1] + slices[i]

Take the max of both options.

The solution

def max_size_slices(slices: list[int]) -> int:
    def solve(arr: list[int], k: int) -> int:
        m = len(arr)
        dp = [[-1] * (k + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = 0

        for i in range(1, m + 1):
            for j in range(1, k + 1):
                dp[i][j] = dp[i - 1][j]
                if i >= 2 and dp[i - 2][j - 1] != -1:
                    dp[i][j] = max(dp[i][j], dp[i - 2][j - 1] + arr[i - 1])
                elif i == 1:
                    dp[i][j] = max(dp[i][j], arr[i - 1])

        return dp[m][k]

    n = len(slices) // 3
    run_a = solve(slices[:-1], n)
    run_b = solve(slices[1:], n)
    return max(run_a, run_b)

Let's walk through what each piece does.

The solve function handles a single linear array. It builds a 2D DP table where dp[i][j] is the maximum sum achievable by selecting exactly j non-adjacent elements from the first i elements. We initialize dp[i][0] = 0 for all i because selecting zero elements always yields a sum of zero. The value -1 marks impossible states (where you cannot select that many non-adjacent elements from the available range).

The transition at each cell considers two options. Skipping element i keeps the answer from dp[i-1][j]. Picking element i means you cannot use element i-1, so you look at dp[i-2][j-1] and add the current value. The max of these two choices fills the cell.

The outer function handles the circular constraint. It splits the problem into two runs, one excluding the last element and one excluding the first, then returns the maximum. This is exactly the same trick used in House Robber II.

Visual walkthrough

The walkthrough shows how the circular array gets split into two linear runs. For each run, the 2D DP table tracks how many non-adjacent elements have been selected so far, filling in cell by cell. The final answer is the maximum across both runs.

Complexity analysis

Time is O(n^2) where n is len(slices) / 3. The array length is 3n, and the DP table for each linear run has 3n rows and n columns, giving O(3n * n) = O(n^2) work per run. Two runs double it, but that is still O(n^2).

Space is O(n^2) for the DP table. You could optimize this to O(n) by only keeping two rows at a time, since each row only depends on the previous two rows. In practice the O(n^2) version is clean and fast enough for the constraints.

The building blocks

1. Circular array to two linear runs

n = len(slices) // 3
run_a = solve(slices[:-1], n)
run_b = solve(slices[1:], n)
return max(run_a, run_b)

This is the same decomposition used in House Robber II. In a circular array, the first and last elements are neighbors. You cannot pick both, so splitting into two subproblems (one without the first, one without the last) guarantees you never violate the circular adjacency constraint. The maximum of the two results is the global optimum.

2. 2D DP for exactly k non-adjacent selections

dp = [[-1] * (k + 1) for _ in range(m + 1)]
for i in range(m + 1):
    dp[i][0] = 0

for i in range(1, m + 1):
    for j in range(1, k + 1):
        dp[i][j] = dp[i - 1][j]
        if i >= 2 and dp[i - 2][j - 1] != -1:
            dp[i][j] = max(dp[i][j], dp[i - 2][j - 1] + arr[i - 1])
        elif i == 1:
            dp[i][j] = max(dp[i][j], arr[i - 1])

This extends the classic House Robber recurrence by adding a second dimension to track exactly how many elements you have picked. The "pick or skip" decision at each element is the same, but now picking increments the count. This building block applies to any problem that asks you to select a fixed number of non-adjacent elements to maximize or minimize some objective.

Edge cases

• All slices equal: any valid selection of n non-adjacent slices gives the same answer. The DP handles this naturally.
• Single round (n=1, 3 slices): you pick one slice. The answer is max(slices).
• Large values concentrated at one spot: greedy might grab the biggest slice, but it could block access to two good neighbors. The DP explores all valid combinations.
• Minimum size (3 slices): the two linear runs each have 2 elements, and you pick 1 from each run. The result is the max element.
• Descending values: the optimal picks are spread out. The non-adjacency constraint prevents consecutive large values from being taken.

From understanding to recall

The reduction from "pizza picking" to "select k non-adjacent elements from a circular array" is the hardest part of this problem. Once you see it, the DP is a natural extension of House Robber. But under interview pressure, making that reduction on the spot requires practice.

Spaced repetition helps you internalize both the reduction step and the 2D DP mechanics. You practice the circular-to-linear split, the 2D table setup, and the pick-or-skip transition independently. After a few reps, the pattern is automatic. When you see "circular array, select k non-adjacent to maximize," you know exactly what to build.

Related posts

• House Robber - The foundational non-adjacent selection problem this builds on
• House Robber II - The circular variant that directly maps to this problem
• Coin Change - Another classic DP problem with optimal substructure

CodeBricks breaks Pizza With 3n Slices into its circular decomposition and 2D non-adjacent selection building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a constrained selection DP problem shows up in your interview, you do not think about it. You just write it.