Maximize Grid Happiness: Profile DP with Bitmask

You are given an m x n grid and two counts: introvertsCount and extrovertsCount. You can place at most that many introverts and extroverts into the grid cells (at most one person per cell, and you do not have to place everyone). Introverts start with 120 happiness and lose 30 for each adjacent neighbor (up, down, left, right). Extroverts start with 40 happiness and gain 20 for each adjacent neighbor. When two people are neighbors, both of them react: the introvert loses 30 and the extrovert gains 20 (or both lose 30 if both are introverts, or both gain 20 if both are extroverts). Maximize the total happiness across all placed people.

This is LeetCode 1659: Maximize Grid Happiness, and it is one of the hardest grid DP problems on the platform. The state space is large, but the grid dimensions are small (m and n are at most 5), which opens the door to profile-based dynamic programming with ternary encoding.

Why this problem matters

Profile DP is a technique where you encode the configuration of an entire row (or column) as a compact state and transition row by row. You see it in tiling problems, placement problems, and constraint satisfaction on grids. This problem adds a twist: you have limited supplies of two person types, and each placement triggers pairwise happiness adjustments. Solving it teaches you how to combine resource tracking with profile transitions, a pattern that transfers to many other hard grid problems.

The key insight

Process the grid cell by cell, left to right and top to bottom. At each cell, you make one of three choices: leave it empty, place an introvert, or place an extrovert. The only information you need from the past is (1) how many introverts and extroverts remain, and (2) what is in the n cells directly above the current cell. That second piece of information is the "profile" of the row above.

Encode each column in the profile as a ternary digit: 0 for empty, 1 for introvert, 2 for extrovert. With n columns, the profile is a number from 0 to 3^n - 1. Since n is at most 5, the maximum profile value is 242 (that is 3^5 - 1), which is very manageable.

The DP state is (cell_index, introverts_remaining, extroverts_remaining, profile). At each cell, you try all three choices, compute the happiness gained (base happiness plus pairwise adjustments with the left neighbor and the neighbor above), update the profile, and take the maximum.

The solution

from functools import lru_cache

def getMaxGridHappiness(m, n, introvertsCount, extrovertsCount):
    def get_val(profile, col):
        return (profile // (3 ** col)) % 3

    def set_val(profile, col, val):
        return profile - get_val(profile, col) * (3 ** col) + val * (3 ** col)

    def calc_adjustment(type_a, type_b):
        diff = 0
        if type_a == 1:
            diff -= 30
        elif type_a == 2:
            diff += 20
        if type_b == 1:
            diff -= 30
        elif type_b == 2:
            diff += 20
        return diff

    total_cells = m * n

    @lru_cache(maxsize=None)
    def dp(pos, in_left, ex_left, profile):
        if pos == total_cells:
            return 0

        row, col = divmod(pos, n)
        best = dp(pos + 1, in_left, ex_left, profile)

        for person_type in [1, 2]:
            if person_type == 1 and in_left == 0:
                continue
            if person_type == 2 and ex_left == 0:
                continue

            gain = 120 if person_type == 1 else 40

            above = get_val(profile, col)
            if above != 0:
                gain += calc_adjustment(person_type, above)

            if col > 0:
                left = get_val(profile, col - 1) if row == divmod(pos - 1, n)[0] else 0
                if left != 0:
                    gain += calc_adjustment(person_type, left)

            new_profile = set_val(profile, col, person_type)
            new_in = in_left - (1 if person_type == 1 else 0)
            new_ex = ex_left - (1 if person_type == 2 else 0)

            result = gain + dp(pos + 1, new_in, new_ex, new_profile)
            best = max(best, result)

        return best

    return dp(0, introvertsCount, extrovertsCount, 0)

The function get_val extracts the ternary digit at a given column from the profile. The function set_val updates a single column in the profile. The function calc_adjustment computes the pairwise happiness change when two adjacent people meet: introverts lose 30 per neighbor and extroverts gain 20 per neighbor, applied from both sides.

The main dp function iterates through every cell position. For each cell, it first tries leaving the cell empty (which does not change the profile at that column but moves to the next cell). Then it tries placing an introvert (if any remain) and an extrovert (if any remain), computing the total happiness gain including neighbor adjustments. The profile is updated so that future cells in the same column know what was placed here.

Visual walkthrough

The profile slides as you process each cell. When you finish the last column of a row and move to the first column of the next row, the profile now represents the completed row above. This is the core mechanism that makes profile DP work on grids.

Complexity analysis

Time: O(m * n * in * ex * 3^n). There are m * n cell positions, up to in + 1 values for introverts remaining, up to ex + 1 values for extroverts remaining, and 3^n possible profiles. At each state, you do O(1) work (three choices with O(1) adjustment calculations). With the constraints (m, n at most 5, in and ex at most 6), the worst case is roughly 5 * 5 * 7 * 7 * 243 = about 297,675 states, which is very fast.

Space: O(m * n * in * ex * 3^n) for the memoization table. Same bound as time, since each state is cached once.

The building blocks

1. Profile-based DP on grids

When a grid has small width (n at most 5 or 6), you can encode the state of an entire row as a single number and transition row by row. This technique goes by many names: profile DP, broken profile DP, or bitmask DP on grids. The key idea is the same: compress a row of decisions into a compact representation and let the DP track that representation as part of its state.

def get_val(profile, col):
    return (profile // (3 ** col)) % 3

def set_val(profile, col, val):
    return profile - get_val(profile, col) * (3 ** col) + val * (3 ** col)

2. Ternary state encoding

Binary bitmasks use two states per cell (0 or 1). Here we need three states per cell (empty, introvert, extrovert), so we use a ternary encoding. Each column position holds a base-3 digit. Extracting and setting individual digits uses division and modulo by powers of 3, just like binary extraction uses shifts and masks.

profile = 0
profile = set_val(profile, 0, 1)
profile = set_val(profile, 1, 2)
profile = set_val(profile, 2, 0)

This gives profile = 1 * 1 + 2 * 3 + 0 * 9 = 7, encoding "introvert in column 0, extrovert in column 1, empty in column 2."

3. Pairwise neighbor happiness adjustment

When you place a person next to an existing neighbor, both people react. Introverts lose 30 and extroverts gain 20 for each new adjacency. The adjustment function handles both directions in a single call.

def calc_adjustment(type_a, type_b):
    diff = 0
    if type_a == 1:
        diff -= 30
    elif type_a == 2:
        diff += 20
    if type_b == 1:
        diff -= 30
    elif type_b == 2:
        diff += 20
    return diff

Two introverts adjacent: -30 + -30 = -60. Two extroverts adjacent: +20 + +20 = +40. One introvert and one extrovert: -30 + +20 = -10.

Edge cases

• Zero people: if both introvertsCount and extrovertsCount are 0, the answer is 0. No one is placed.
• All introverts, 1x1 grid: a single introvert with no neighbors gets the full 120 happiness. No adjacency penalty applies.
• Extroverts only: you want to pack extroverts as tightly as possible to maximize adjacency bonuses, but each extrovert only adds 40 base happiness. Placing more is not always better if the grid is sparse.
• Full grid of introverts: each interior introvert has up to 4 neighbors, losing 120 total (4 * 30). That drops their net happiness to 0. Corner and edge introverts fare better. Sometimes leaving cells empty is optimal.
• m = 1 (single row): the profile degenerates to just the current row state, and each cell only has a left neighbor. The problem simplifies to a 1D DP.
• Large extrovert count with small grid: you cannot place more people than cells. The DP naturally handles this because pos advances to total_cells and returns 0.

From understanding to recall

You now understand how to flatten a 2D grid into a cell sequence, encode the row state as a ternary profile, track remaining introverts and extroverts, and compute pairwise neighbor adjustments. But reconstructing this solution under interview pressure is a different challenge entirely.

The tricky parts are: remembering to track the profile as a ternary number (not binary), correctly computing the two-sided adjustment when a person is placed next to a neighbor, and handling the transition between rows (when column wraps from n-1 back to 0). These details fade after a week or two.

Profile DP with ternary encoding is one of the more advanced building blocks in the CodeBricks system. You drill it with spaced repetition until the mechanics of extracting digits, computing adjustments, and updating profiles become automatic. Once the profile DP template is locked in, any grid placement problem with small width becomes approachable.

Related posts

• Unique Paths - Foundation grid DP problem that teaches row-by-row processing
• Dungeon Game - Grid DP with constraints on state transitions
• Burst Balloons - Interval DP that requires careful state definition, similar complexity

Profile DP with ternary encoding is a powerful technique that unlocks a family of hard grid problems. Understanding it deeply, and being able to reproduce it from memory, is one of the highest-leverage investments you can make in your problem-solving toolkit.