< Back




1659. Maximize Grid Happiness

We're given a grid of size m * n, and a number of introverts and extroverts. We're asked to maximize
the introverts' and extroverts' happiness across the grid. When we place an introvert, it starts out
at 120 happiness, however, if there are neighbors it loses 30 happiness per neighbor. When we place
an extrovert, it starts out at 40 happiness, and it gains 20 happiness per neighbor.

Using top-down dynamic programming, we start at the top-left of the grid and work our way down to
the bottom-right of the grid, making three decisions recursively at each cell. The first choice we
can make is to skip placing an introvert or an extrovert. The second choice is to place an introvert
and the third choice is to place an extrovert.

For placing an introvert and an extrovert, we calculate the total that making this choice is going
to add to the overall answer. If we place an extrovert, we check our neighbors above and to our
left. If we have neighbors, for an introvert we lose happiness, for an extrovert we gain happiness.
If our neighbor is an introvert, that introvert also loses happiness - we account for this in our
total. If our neighbor is an extrovert, that extrovert also gains happiness - we account for this in
our total.

We choose the maximum between these choices, skipping, adding an introvert at the current cell, or
adding an extrovert at the current cell. Our recursion will terminate with these base cases:

  * Going past the last row (i == m)
  * Going past the last column (j == n)
  * Running out of introverts and extroverts to place

The solution is as follows:


  class Solution:
      def getMaxGridHappiness(
          self, m: int, n: int, introvertsCount: int, extrovertsCount: int
      ) -> int:
          @cache
          def dp(i: int, j: int, introverts: int, extroverts: int, prev: tuple) -> int:
              if i == m:
                  return 0
              elif j == n:
                  return dp(i + 1, 0, introverts, extroverts, prev)
              elif not introverts and not extroverts:
                  return 0

              curr = prev[:j] + (0,) + prev[j + 1 :]
              ans = dp(i, j + 1, introverts, extroverts, curr)

              if introverts:
                  total = 120

                  if i and prev[j]:
                      total -= 30

                      if prev[j] == 1:
                          total -= 30
                      else:
                          total += 20

                  if j and prev[j - 1]:
                      total -= 30

                      if prev[j - 1] == 1:
                          total -= 30
                      else:
                          total += 20

                  curr = prev[:j] + (1,) + prev[j + 1 :]
                  ans = max(ans, dp(i, j + 1, introverts - 1, extroverts, curr) + total)

              if extroverts:
                  total = 40

                  if i and prev[j]:
                      total += 20

                      if prev[j] == 1:
                          total -= 30
                      else:
                          total += 20

                  if j and prev[j - 1]:
                      total += 20

                      if prev[j - 1] == 1:
                          total -= 30
                      else:
                          total += 20

                  curr = prev[:j] + (2,) + prev[j + 1 :]
                  ans = max(ans, dp(i, j + 1, introverts, extroverts - 1, curr) + total)

              return ans

          return dp(0, 0, introvertsCount, extrovertsCount, (0,) * n)


_ Time Complexity:

  O(m^2 * n^2) - Where m is the number of rows and n is the number of columns.

_ Space Complexity:

  O(m^2 * n^2) - Our recursive call stack can reach this size.