最大化网格幸福感

难度: Hard

给你四个整数 m、n、introvertsCount 和 extrovertsCount 。有一个 m x n 网格，和两种类型的人：内向的人和外向的人。总共有 introvertsCount 个内向的人和 extrovertsCount 个外向的人。

请你决定网格中应当居住多少人，并为每个人分配一个网格单元。注意，不必让所有人都生活在网格中。

每个人的 幸福感 计算如下：

内向的人开始时有 120 个幸福感，但每存在一个邻居（内向的或外向的）他都会失去 30 个幸福感。
外向的人开始时有 40 个幸福感，每存在一个邻居（内向的或外向的）他都会得到 20 个幸福感。

邻居是指居住在一个人所在单元的上、下、左、右四个直接相邻的单元中的其他人。

网格幸福感 是每个人幸福感的总和。返回 最大可能的网格幸福感 。

示例 1：

输入：m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2
输出：240
解释：假设网格坐标 (row, column) 从 1 开始编号。
将内向的人放置在单元 (1,1) ，将外向的人放置在单元 (1,3) 和 (2,3) 。
- 位于 (1,1) 的内向的人的幸福感：120（初始幸福感）- (0 * 30)（0 位邻居）= 120
- 位于 (1,3) 的外向的人的幸福感：40（初始幸福感）+ (1 * 20)（1 位邻居）= 60
- 位于 (2,3) 的外向的人的幸福感：40（初始幸福感）+ (1 * 20)（1 位邻居）= 60
网格幸福感为：120 + 60 + 60 = 240
上图展示该示例对应网格中每个人的幸福感。内向的人在浅绿色单元中，而外向的人在浅紫色单元中。

示例 2：

输入：m = 3, n = 1, introvertsCount = 2, extrovertsCount = 1
输出：260
解释：将内向的人放置在单元 (1,1) 和 (3,1) ，将外向的人放置在单元 (2,1) 。
- 位于 (1,1) 的内向的人的幸福感：120（初始幸福感）- (1 * 30)（1 位邻居）= 90
- 位于 (2,1) 的外向的人的幸福感：40（初始幸福感）+ (2 * 20)（2 位邻居）= 80
- 位于 (3,1) 的内向的人的幸福感：120（初始幸福感）- (1 * 30)（1 位邻居）= 90
网格幸福感为 90 + 80 + 90 = 260

示例 3：

输入：m = 2, n = 2, introvertsCount = 4, extrovertsCount = 0
输出：240

提示：

1 <= m, n <= 5
0 <= introvertsCount, extrovertsCount <= min(m * n, 6)

Submission

运行时间: 844 ms

内存: 130.9 MB

class Solution:
    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:
        # T = 3 ** n
        # score = [
        #     [0,   0,   0],
        #     [0, -60, -10],
        #     [0, -10,  40],
        # ]
        # incnt = [0 for _ in range(T)]
        # excnt = [0 for _ in range(T)]
        # inner = [0 for _ in range(T)]
        # inter = [[0 for _ in range(T)] for _ in range(T)]
        # bits = [[0 for _ in range(n)] for _ in range(T)]

        # for mask in range(T) :
        #     tmp = mask
        #     for i in range(n) :
        #         bits[mask][i] = x = tmp % 3
        #         tmp //= 3
        #         if x == 1 :
        #             incnt[mask] += 1
        #             inner[mask] += 120
        #         elif x == 2 :
        #             excnt[mask] += 1
        #             inner[mask] += 40
        #         if i > 0 :
        #             inner[mask] += score[x][bits[mask][i - 1]]
        #         if not tmp :
        #             break
        # for i in range(T) :
        #     for j in range(T) :
        #         inter[i][j] = sum(map(lambda x: score[x[0]][x[1]], zip(bits[i], bits[j])))
        
        # @cache
        # def dfs(row, premask, inc, exc) :
        #     if row == m or (not inc and not exc) :
        #         return 0
        #     res = 0
        #     for mask in range(T) :
        #         if incnt[mask] <= inc and excnt[mask] <= exc :
        #             if res < (tmp := dfs(row + 1, mask, inc - incnt[mask], exc - excnt[mask]) + inner[mask] + inter[premask][mask]) :
        #                 res = tmp
        #     return res
        # return dfs(0, 0, introvertsCount, extrovertsCount)


        T = 3 ** n
        score = [
            [0,   0,   0],
            [0, -60, -10],
            [0, -10,  40],
        ]
        p = T // 3

        @cache
        def dfs(pos, mask, inc, exc) :
            if pos == n * m or (not inc and not exc) :
                return 0
            up = mask // p
            if pos % n :
                left = mask % 3
            else :
                left = 0
            res = 0
            for i in range(3) :
                if (i == 1 and inc == 0) or (i == 2 and exc == 0) :
                    continue
                next_mask = mask % p * 3 + i
                if i == 1 :
                    tmp = 120 + dfs(pos + 1, next_mask, inc - 1, exc) + score[up][i] + score[left][i]
                elif i == 2 :
                    tmp = 40 + dfs(pos + 1, next_mask, inc, exc - 1) + score[up][i] + score[left][i]
                else :
                    tmp = dfs(pos + 1, next_mask, inc, exc)
                if res < tmp :
                    res = tmp
            return res
                
        return dfs(0, 0, introvertsCount, extrovertsCount)

Explain

这个问题通过动态规划的方法来解决，特别是使用状态压缩和记忆化搜索来处理。考虑到网格的大小限制（最大为5x5），可以使用三进制表示状态（0表示无人，1表示内向的人，2表示外向的人）。每一个位置的状态依赖于它左边和上面的格子。解决方法是递归地尝试每个位置可能的人配置，然后计算由此产生的幸福值，并将这些值累加。递归的终止条件是当填满了所有的格子或者没有更多的人可供配置。使用记忆化来保存已经计算过的状态的结果，从而避免重复计算。

时间复杂度: O((n*m) * (3^n) * (introvertsCount+1) * (extrovertsCount+1))

空间复杂度: O((n*m) * (3^n) * (introvertsCount+1) * (extrovertsCount+1))

class Solution:
    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:
        T = 3 ** n  # Total number of states for one row
        score = [
            [0,   0,   0],
            [0, -60, -10],
            [0, -10,  40],
        ]
        p = T // 3

        @cache
        def dfs(pos, mask, inc, exc) :
            if pos == n * m or (not inc and not exc) :
                return 0
            up = mask // p  # State of the cell directly above
            if pos % n :
                left = mask % 3  # State of the cell to the left
            else :
                left = 0
            res = 0
            for i in range(3) :
                if (i == 1 and inc == 0) or (i == 2 and exc == 0) :
                    continue
                next_mask = mask % p * 3 + i
                if i == 1 :
                    tmp = 120 + dfs(pos + 1, next_mask, inc - 1, exc) + score[up][i] + score[left][i]
                elif i == 2 :
                    tmp = 40 + dfs(pos + 1, next_mask, inc, exc - 1) + score[up][i] + score[left][i]
                else :
                    tmp = dfs(pos + 1, next_mask, inc, exc)
                if res < tmp :
                    res = tmp
            return res
                
        return dfs(0, 0, introvertsCount, extrovertsCount)

Explore

在这个动态规划问题中，使用三进制来表示每行的状态是因为每个格子有三种可能的状态：无人(0)、内向的人(1)和外向的人(2)。由于网格的列数n最大为5，因此一行的状态可以使用一个三进制数表示，这样的表示可以精确地描述各个位置的人员配置。这种方法允许我们使用一个整数来编码和解码整行的状态，从而简化状态的管理和转移计算。

在递归函数中，`next_mask = mask % p * 3 + i` 这行代码的功能是更新状态以反映在当前位置放置一个新的人（无人、内向或外向）。这里，`mask % p` 将当前行状态向右移动一位，相当于删除了最左侧的格子状态；乘以3是为了在最右侧加入一个新的空位；加上i是在这个新空位上设置当前格子的人员状态（i为0、1或2）。这种方式有效地将一行的状态从当前位置转移到下一个位置，同时更新了新的人员配置。

将问题分解为处理每个单元格的状态而不是整个网格的状态，主要是出于计算效率和实现的简便性的考虑。如果处理整个网格的状态，状态空间会变得非常大，因为需要为网格中的每个位置考虑所有可能的人员配置。相反，通过逐个处理单元格，可以使用动态规划的递归方法逐步构建解决方案，同时可以利用行与行之间的关系（通过状态转移）来减少重复计算。这种方法使得问题的解决更加模块化和可管理。

当 `pos % n == 0` 时，意味着当前位置位于网格的新一行的开始。在这种情况下，将 `left` 设为0是因为新行的第一个格子左边没有其他格子，因此左边的影响应该是0（无人状态）。这是处理边界条件的一种方式，确保在行的开始时不会错误地计算来自不存在的左侧邻居的影响。这样可以正确处理每行开始时的状态转移和幸福值计算。