原文链接: https://leetcode-cn.com/problems/maximize-grid-happiness

英文原文

You are given four integers, m, n, introvertsCount, and extrovertsCount. You have an m x n grid, and there are two types of people: introverts and extroverts. There are introvertsCount introverts and extrovertsCount extroverts.

You should decide how many people you want to live in the grid and assign each of them one grid cell. Note that you do not have to have all the people living in the grid.

The happiness of each person is calculated as follows:

• Introverts start with 120 happiness and lose 30 happiness for each neighbor (introvert or extrovert).
• Extroverts start with 40 happiness and gain 20 happiness for each neighbor (introvert or extrovert).

Neighbors live in the directly adjacent cells north, east, south, and west of a person's cell.

The grid happiness is the sum of each person's happiness. Return the maximum possible grid happiness.

 

Example 1:

Input: m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2
Output: 240
Explanation: Assume the grid is 1-indexed with coordinates (row, column).
We can put the introvert in cell (1,1) and put the extroverts in cells (1,3) and (2,3).
- Introvert at (1,1) happiness: 120 (starting happiness) - (0 * 30) (0 neighbors) = 120
- Extrovert at (1,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60
- Extrovert at (2,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60
The grid happiness is 120 + 60 + 60 = 240.
The above figure shows the grid in this example with each person's happiness. The introvert stays in the light green cell while the extroverts live on the light purple cells.

Example 2:

Input: m = 3, n = 1, introvertsCount = 2, extrovertsCount = 1
Output: 260
Explanation: Place the two introverts in (1,1) and (3,1) and the extrovert at (2,1).
- Introvert at (1,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90
- Extrovert at (2,1) happiness: 40 (starting happiness) + (2 * 20) (2 neighbors) = 80
- Introvert at (3,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90
The grid happiness is 90 + 80 + 90 = 260.

Example 3:

Input: m = 2, n = 2, introvertsCount = 4, extrovertsCount = 0
Output: 240

 

Constraints:

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

中文题目

给你四个整数 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)

通过代码

高赞题解

前言

为了叙述方便，使用 $\textit{nx}$ 和 $\textit{wx}$ 分别表示内向和外向的人数，并使用「分数」代替「幸福感」。

本题的数据范围较小，所以比较容易想到搜索 + 回溯的暴力方法。但数据真的有这么小吗？在最坏情况下，$m=n=5$ 并且 $\textit{nx}=\textit{wx}=6$，那么在 $5\times5=25$ 个位置中选择 $6$ 个分配给内向的人，再从 $25-6=19$ 个位置中选择 $6$ 个分配给外向的人，那么使用组合数可以计算出不同的方案数为：

$$
\binom{25}{6} \binom{19}{6} = 4.8 \times 10^9
$$

即使可以 $O(1)$ 的时间计算出每一种方案对应的分数，也会很容易导致超出时间限制。因此，我们需要减少搜索空间。由于每一个位置只有「空」「内向」「外向」三种状态，我们可以将这三个状态分别编码为 $0, 1, 2$，并用一个长度（位数）为 $n$ 的三进制数对一行的状态进行编码。这样一来，我们就可以使用基于状态压缩的动态规划了。

方法一：按行进行状态压缩

思路与算法

如果我们以「行」为单位进行动态规划，那么在计算分数时，我们可以将其分成两个部分：

-「行内分数」：在同一行内每个人的分数，内向 $120$ 分，外向 $40$ 分；以及由于两人相邻（在同一行内，即左右相邻）贡献的额外分数，两个内向 $-60$ 分，两个外向 $40$ 分，其余情况 $-10$ 分；

-「行外分数」：由于两人相邻（在不同行内，即上下相邻）贡献的额外分数，同理为 $-60,40,-10$ 分中的一种。

根据上面的拆分，如果我们规定「行外分数」由相邻两行中的后一行负责计算，那么在我们枚举当前行对应的三进制表示 $\textit{mask}$ 时，它需要计算其与前一行之间的「行外分数」，因此我们可以设计出动态规划中的状态：

令 $f(\textit{mask}_L, \textit{row}, \textit{nx}, \textit{wx})$ 表示当我们枚举到第 $\textit{row}$ 行且之前的行已经枚举完成，第 $\textit{row}-1$ 行的状态为 $\textit{mask}_L$，还剩余 $\textit{nx}$ 个内向的人以及 $\textit{wx}$ 个外向的人的情况下，从第 $\textit{row}$ 行开始往后的所有行可以获得的最大分数。

有了这样的状态表示，当我们在枚举第 $\textit{row}$ 行的状态 $\textit{mask}$ 时，就可以得到状态转移方程：

$$
\begin{aligned}
& f(\textit{mask}_L, \textit{row}, \textit{nx}, \textit{wx}) = \max \big{ \
& \qquad f(\textit{mask}, \textit{row}+1, \textit{nx}-\text{count}_\textit{nx}(\textit{mask}), \textit{wx}-\text{count}_\textit{wx}(\textit{mask})) \
& \qquad \qquad + \text{score}_\textit{inner}(\textit{mask}) \
& \qquad \qquad + \text{score}_\textit{outer}(\textit{mask}, \textit{mask}_L) \
& \big}
\end{aligned}
$$

这里使用到的函数很多，我们逐一解释：

• $\text{count}_\textit{nx}(\textit{mask})$ 表示状态 $\textit{mask}$ 中有多少个内向的人，即有多少个 $1$；

• $\text{count}_\textit{wx}(\textit{mask})$ 表示状态 $\textit{mask}$ 中有多少个外向的人，即有多少个 $2$；

• $\text{score}_\textit{inner}(\textit{mask})$ 表示状态 $\textit{mask}$ 的「行内分数」；

• $\text{score}_\textit{outer}(\textit{mask}, \textit{mask}_L)$ 表示状态 $\textit{mask}$ 和 $\textit{mask}_L$ 之间的「行外分数」。

也就是说，我们枚举第 $\textit{row}$ 行的状态 $\textit{mask}$，计算「行内分数」以及「行外分数」，并扣除该行分别使用的内向和外向的人数，再转移到下一行。需要注意的是，必须要保证使用的内向和外向的人数分别不能超过剩余的内向和外向的人数。

由于我们不必使用完所有的人，因此边界条件可以有以下两种：

• 当 $\textit{nx}=\textit{wx}=0$ 时，已经使用完了所有的人，对应的 $f$ 值为 $0$；

• 当 $\textit{row}=m$ 时，已经枚举完了所有的行，无论 $\textit{nx}$ 和 $\textit{wx}$ 的值为多少，都是一种满足要求的方案，对应的 $f$ 值也为 $0$。

此时，我们只要调用 $f(0, 0, \textit{nx}, \textit{wx})$ 并使用记忆化搜索的方法实现上述状态转移方程，即可得到最终的答案。为什么初始时 $\textit{mask}_L$ 的值为 $0$？我们可以看成第 $0$ 行的上方有一个「虚拟」的第 $-1$ 行，其中没有任何人，对应的状态表示即为 $0$。

细节

使用上述的状态转移方程便编写代码很容易超出时间限制，这是因为计算 $\text{count}_\textit{nx}(\textit{mask})$，$\text{count}_\textit{wx}(\textit{mask})$，$\text{score}_\textit{inner}(\textit{mask})$，$\text{score}_\textit{outer}(\textit{mask}, \textit{mask}_L)$ 的时间复杂度可能较高，并且会涉及到很多不必要的重复操作。由于 $\textit{mask}$ 本身的数量有限，它对应的十进制值在 $[0, 3^n)$ 的范围内，因此我们可以「预处理」出所有的这些值，而在状态转移时，就可以 $O(1)$ 计算出结果了。具体可以参考下面给出的代码，预处理计算了：

• 每一个 $\textit{mask}$ 对应的三进制表示，存放在数组 $\texttt{mask_span}$ 中；

• 所有的 $\text{count}_\textit{nx}(\textit{mask})$ 和 $\text{count}_\textit{wx}(\textit{mask})$，分别存放在数组 $\texttt{nx_inner}$ 以及 $\texttt{wx_inner}$ 中；

• 所有的 $\text{score}_\textit{inner}(\textit{mask})$，存放在数组 $\texttt{score_inner}$ 中；

• 所有的 $\text{score}_\textit{outer}(\textit{mask}, \textit{mask}_L)$，存放在数组 $\texttt{score_outer}$ 中。

由于本方法的时间复杂度较高，使用 Python 较难通过。

代码

[sol1-C++]
class Solution {
private:
    // 预处理：每一个 mask 的三进制表示
    int mask_span[729][6];
    // dp[上一行的 mask][当前处理到的行][剩余的内向人数][剩余的外向人数]
    int dp[729][6][7][7];
    // 预处理：每一个 mask 包含的内向人数，外向人数，行内得分（只统计 mask 本身的得分，不包括它与上一行的），行外得分
    int nx_inner[729], wx_inner[729], score_inner[729], score_outer[729][729];
    // n3 = n^3
    int m, n, n3;
    
public:
    // 如果 x 和 y 相邻，需要加上的分数
    inline int calc(int x, int y) {
        if (x == 0 || y == 0) {
            return 0;
        }
        // 例如两个内向的人，每个人要 -30，一共 -60，下同
        if (x == 1 && y == 1) {
            return -60;
        }
        if (x == 2 && y == 2) {
            return 40;
        }
        return -10;
    }
    
    int getMaxGridHappiness(int m, int n, int nx, int wx) {
        this->m = m;
        this->n = n;
        this->n3 = pow(3, n);
        
        // 预处理
        for (int mask = 0; mask < n3; ++mask) {
            for (int mask_tmp = mask, i = 0; i < n; ++i) {
                mask_span[mask][i] = mask_tmp % 3;
                mask_tmp /= 3;
            }
            nx_inner[mask] = wx_inner[mask] = score_inner[mask] = 0;
            for (int i = 0; i < n; ++i) {
                if (mask_span[mask][i] != 0) {
                    // 个人分数
                    if (mask_span[mask][i] == 1) {
                        ++nx_inner[mask];
                        score_inner[mask] += 120;
                    }
                    else if (mask_span[mask][i] == 2) {
                        ++wx_inner[mask];
                        score_inner[mask] += 40;
                    }
                    // 行内分数
                    if (i - 1 >= 0) {
                        score_inner[mask] += calc(mask_span[mask][i], mask_span[mask][i - 1]);
                    }
                }
            }
        }
        // 行外分数
        for (int mask0 = 0; mask0 < n3; ++mask0) {
            for (int mask1 = 0; mask1 < n3; ++mask1) {
                score_outer[mask0][mask1] = 0;
                for (int i = 0; i < n; ++i) {
                    score_outer[mask0][mask1] += calc(mask_span[mask0][i], mask_span[mask1][i]);
                }
            }
        }
        
        memset(dp, -1, sizeof(dp));
        return dfs(0, 0, nx, wx);
    }
    
    
    // dfs(上一行的 mask，当前处理到的行，剩余的内向人数，剩余的外向人数）
    int dfs(int mask_last, int row, int nx, int wx) {
        // 边界条件：如果已经处理完，或者没有人了
        if (row == m || nx + wx == 0) {
            return 0;
        }
        // 记忆化
        if (dp[mask_last][row][nx][wx] != -1) {
            return dp[mask_last][row][nx][wx];
        }
        
        int best = 0;
        for (int mask = 0; mask < n3; ++mask) {
            if (nx_inner[mask] > nx || wx_inner[mask] > wx) {
                continue;
            }
            int score = score_inner[mask] + score_outer[mask][mask_last];
            best = max(best, score + dfs(mask, row + 1, nx - nx_inner[mask], wx - wx_inner[mask]));
        }
        
        return dp[mask_last][row][nx][wx] = best;
    }
};

复杂度分析

• 时间复杂度：分为以下部分：

  • 预处理部分计算 $\textit{mask}$ 的三进制表示，$\text{count}_\textit{nx}(\textit{mask})$，$\text{count}_\textit{wx}(\textit{mask})$，$\text{score}_\textit{inner}(\textit{mask})$ 的时间复杂度为 $O(n \cdot 3^n)$；
  • 预处理部分计算 $\text{score}_\textit{outer}(\textit{mask}, \textit{mask}_L)$ 的时间复杂度为 $O(n \cdot 3^{2n})$；
  • 记忆化搜索部分的状态总数为 $O(m\cdot\textit{wx}\cdot\textit{nx}\cdot3^n)$，状态转移时需要枚举 $O(3^n)$ 的状态，转移的时间复杂度为 $O(1)$，总时间复杂度为 $O(m\cdot\textit{wx}\cdot\textit{nx}\cdot3^{2n})$。

  第一项在渐进意义下小于第二项，可以忽略，因此总时间复杂度为 $O\big((m\cdot\textit{wx}\cdot\textit{nx}+n)\cdot3^{2n}\big)$。

• 空间复杂度：分为以下部分：

  • 预处理部分计算 $\textit{mask}$ 的三进制表示需要的空间为 $O(n \cdot 3^n)$；
  • 预处理部分计算 $\text{count}_\textit{nx}(\textit{mask})$，$\text{count}_\textit{wx}(\textit{mask})$，$\text{score}_\textit{inner}(\textit{mask})$ 需要的空间为 $O(3^n)$；
  • 预处理部分计算 $\text{score}_\textit{outer}(\textit{mask}, \textit{mask}_L)$ 需要的空间为 $O(3^{2n})$；
  • 记忆化搜索部分的状态总数为 $O(m\cdot\textit{wx}\cdot\textit{nx}\cdot3^n)$，即为需要的空间。

  虽然所有其余项在渐进意义下都小于第三项，但为了表示空间与所有变量之间的关系，将总空间复杂度写为 $O\big((m\cdot\textit{wx}\cdot\textit{nx}+n)\cdot3^{n} + 3^{2n}\big)$。

方法二：按轮廓线进行状态压缩

思路与算法

这是一种在竞赛中会用到的动态规划方法，称之为「轮廓线动态规划」。当我们在一个二维矩阵上进行动态规划，并且数据规模不大、状态的表示方法有限（可以使用状态压缩的方法）、可以通过当前位置与其上方和左侧的位置计算状态转移方程，那么就可以考虑使用轮廓线动态规划。在力扣平台上，这一类的题目非常少，类似的只有一道力扣杯的题目 LCP 04. 覆盖。这里感谢 @newhar 指出，还有一道题目 1349. 参加考试的最大学生数。

下面左侧的图展示了轮廓线动态规划需要维护的状态以及它的转移过程。如果我们枚举到了当前位置（绿色）的状态，我们需要利用到从该位置上一行位于相同列的位置开始，到该位置的上一个位置结束的 $n$ 个状态的状态压缩表示（蓝色）。这样一来，我们可以通过当前位置与编号为 $0$ 的位置（也就是上下相邻），以及编号为 $n-1$ 的位置（左右相邻）之间的关系，计算出因为两人相邻贡献的额外分数。如果我们规定上下相邻的两人由下面的人负责计算贡献，左右相邻的人由右边的人负责计算贡献，那么我们就可以按照行优先的顺序依次枚举每一个位置，并进行状态转移了。

{:width=600}

那么我们为什么要存储连续的 $n$ 个状态，而不是当前位置的上方和左侧 $2$ 个状态呢？看上去我们额外存储了 $n-2$ 个状态，但我们可以想一下，如果只存储 $2$ 个状态会造成什么后果。参考上面右侧的图，当我们枚举到下一个位置时，如果我们存储的是连续的 $n$ 个状态，那么我们将上面左侧编号 $0$ 的位置移除，再添加前一个位置，就可以得到下一个位置对应的 $n$ 个状态。但加入我们只存储状态 $0$ 和 $n-1$，那么在枚举到下一个位置时，状态 $n-1$ 可以通过上一个位置得到，但状态 $0$ 却是未知的了。这也是轮廓线动态规划的妙处所在。

因此我们可以设计出动态规划中的状态：

令 $f(\textit{pos}, \textit{borderline}, \textit{nx}, \textit{wx})$ 表示当我们枚举到第 $\textit{pos}$ 个位置且之前的位置已经枚举完成，该位置的前 $n$ 个位置的状态压缩为 $\textit{borderline}$，还剩余 $\textit{nx}$ 个内向的人以及 $\textit{wx}$ 个外向的人的情况下，从第 $\textit{pos}$ 个位置开始往后的所有位置可以获得的最大分数。

有了这样的状态表示，当我们在枚举第 $\textit{pos}$ 个位置的状态时，考虑三种情况：

• 第 $\textit{pos}$ 个位置为「空」，那么我们直接进行状态转移：

  $$
  f(\textit{pos}, \textit{borderline}, \textit{nx}, \textit{wx}) = f(\textit{pos}+1, \textit{borderline}\backslash0, \textit{nx}, \textit{wx})
  $$

  这里 $\textit{borderline}\backslash0$ 表示将 $\textit{borderline}$ 最前面的第 $0$ 个位置移除，再在最后面添加状态 $0$ 得到的结果。它的计算方法很简单，我们只需要将 $\textit{borderline}$ 的最高位移除，剩余部分乘 $3$，再加上 $0$ 即可，即：

  $$
  \textit{borderline}\backslash0 = \textit{borderline} % 3^{n-1} \times 3 + 0
  $$

  其中 $%$ 表示取模运算。下面的状态转移中会使用到 $\textit{borderline}\backslash1$ 以及 $\textit{borderline}\backslash2$，计算方法相同。

• 第 $\textit{pos}$ 个位置为「内向」，我们需要增加内向的分数 $120$，并且计算其与两个相邻位置（上方以及左侧）的额外分数。在转移之前，需要保证 $\textit{nx}$ 不为 $0$：

  $$
  \begin{aligned}
  f(\textit{pos}, \textit{borderline}, \textit{nx}, \textit{wx}) = 120 &+ \text{calc}(1, \textit{borderline}[0]) \
  &+ \text{calc}(1, \textit{borderline}[n-1]) \
  &+ f(\textit{pos}+1, \textit{borderline}\backslash1, \textit{nx}-1, \textit{wx})
  \end{aligned}
  $$

  其中函数 $\text{calc}(x, y)$ 表示两个相邻位置的状态分别为 $x$ 和 $y$ 时的额外分数，当方法一中也使用到了类似的函数：其中有一个为 $0$ 记 $0$ 分，均为 $1$ 记 $-60$ 分，均为 $2$ 记 $40$ 分，其余情况记 $-10$ 分。

• 第 $\textit{pos}$ 个位置为「外向」，我们需要增加外向的分数 $40$，并且计算其与两个相邻位置（上方以及左侧）的额外分数。在转移之前，需要保证 $\textit{wx}$ 不为 $0$：

  $$
  \begin{aligned}
  f(\textit{pos}, \textit{borderline}, \textit{nx}, \textit{wx}) = 40 &+ \text{calc}(2, \textit{borderline}[0]) \
  &+ \text{calc}(2, \textit{borderline}[n-1]) \
  &+ f(\textit{pos}+1, \textit{borderline}\backslash2, \textit{nx}, \textit{wx}-1)
  \end{aligned}
  $$

与方法一类似，边界条件有两种：

• 当 $\textit{nx}=\textit{wx}=0$ 时，已经使用完了所有的人，对应的 $f$ 值为 $0$；

• 当 $\textit{pos}=mn$ 时，已经枚举完了所有的位置，无论 $\textit{nx}$ 和 $\textit{wx}$ 的值为多少，都是一种满足要求的方案，对应的 $f$ 值也为 $0$。

细节

方法二中的细节比较多，我们逐一进行分析。

首先是状态转移时的特殊情况。考虑下面左侧的图，若当前枚举到的位置位于首列，那么它是没有左侧相邻位置的，即它与存储的第 $n-1$ 个状态并不相邻，因此状态转移方程中对应的 $\text{calc}(1, \textit{borderline}[n-1])$ 以及 $\text{calc}(2, \textit{borderline}[n-1])$ 项不能带入计算。

再考虑下面右侧的图，若当前枚举到的位置位于首行，那么它是没有上方相邻位置的，但我们可以使用与方法一中相同的处理形式，看成其上方有一个「虚拟」的第 $-1$ 行，该行的所有状态均为 $0$。这也告诉了我们如果使用记忆化搜索的方法实现方法二，那么只需要调用 $f(0, 0, \textit{nx}, \textit{wx})$ 即可得到最终的答案，这里第二个参数中的 $0$ 就表示虚拟行包含 $n$ 个 $0$。

{:width=600}

此外，我们也可以预处理出一些结果，使得可以 $O(1)$ 的时间进行状态转移：

• 每一个 $\textit{mask}$ 对应的三进制表示，存放在数组 $\texttt{mask_span}$ 中。注意由于我们在进行十进制转三进制时，首先得到的是低位，而在方法二的状态表示中，低位的编号反而更大（最低位编号为 $n-1$，最高位编号为 $0$），因此我们要需要注意将三进制表示以正确的顺序进行存储；

• 所有的 $\textit{mask}\backslash0$，$\textit{mask}\backslash1$，$\textit{mask}\backslash2$，存放在数组 $\texttt{truncate}$ 中。

代码

[sol2-C++]
class Solution {
private:
    // 预处理：每一个 mask 的三进制表示
    int mask_span[729][6];
    // dp[位置][轮廓线上的 mask][剩余的内向人数][剩余的外向人数]
    int dp[25][729][7][7];
    // 预处理：每一个 mask 去除最高位、乘 3、加上新的最低位的结果
    int truncate[729][3];
    // n3 = n^3
    int m, n, n3;
    
public:
    // 如果 x 和 y 相邻，需要加上的分数
    inline int calc(int x, int y) {
        if (x == 0 || y == 0) {
            return 0;
        }
        // 例如两个内向的人，每个人要 -30，一共 -60，下同
        if (x == 1 && y == 1) {
            return -60;
        }
        if (x == 2 && y == 2) {
            return 40;
        }
        return -10;
    }
    
    int getMaxGridHappiness(int m, int n, int nx, int wx) {
        this->m = m;
        this->n = n;
        this->n3 = pow(3, n);
        
        // 预处理
        int highest = this->n3 / 3;
        for (int mask = 0; mask < n3; ++mask) {
            for (int mask_tmp = mask, i = 0; i < n; ++i) {
                // 与方法一不同的是，这里需要反过来存储，这样 [0] 对应最高位，[n-1] 对应最低位
                mask_span[mask][n - i - 1] = mask_tmp % 3;
                mask_tmp /= 3;
            }
            truncate[mask][0] = mask % highest * 3;
            truncate[mask][1] = mask % highest * 3 + 1;
            truncate[mask][2] = mask % highest * 3 + 2;
        }
        
        memset(dp, -1, sizeof(dp));
        return dfs(0, 0, nx, wx);
    }
    
    
    // dfs(位置，轮廓线上的 mask，剩余的内向人数，剩余的外向人数)
    int dfs(int pos, int borderline, int nx, int wx) {
        // 边界条件：如果已经处理完，或者没有人了
        if (pos == m * n || nx + wx == 0) {
            return 0;
        }
        // 记忆化
        if (dp[pos][borderline][nx][wx] != -1) {
            return dp[pos][borderline][nx][wx];
        }
        
        int x = pos / n, y = pos % n;
        
        // 什么都不做
        int best = dfs(pos + 1, truncate[borderline][0], nx, wx);
        // 放一个内向的人
        if (nx > 0) {
            best = max(best, 120 + calc(1, mask_span[borderline][0]) \
                                 + (y == 0 ? 0 : calc(1, mask_span[borderline][n - 1])) \
                                 + dfs(pos + 1, truncate[borderline][1], nx - 1, wx));
        }
        // 放一个外向的人
        if (wx > 0) {
            best = max(best, 40 + calc(2, mask_span[borderline][0]) \
                                + (y == 0 ? 0 : calc(2, mask_span[borderline][n - 1])) \
                                + dfs(pos + 1, truncate[borderline][2], nx, wx - 1));
        }

        return dp[pos][borderline][nx][wx] = best;
    }
};

[sol2-Python3]
class Solution:
    def getMaxGridHappiness(self, m: int, n: int, nx: int, wx: int) -> int:
        # 如果 x 和 y 相邻，需要加上的分数
        def calc(x: int, y: int) -> int:
            if x == 0 or y == 0:
                return 0
            # 例如两个内向的人，每个人要 -30，一共 -60，下同
            if x == 1 and y == 1:
                return -60
            if x == 2 and y == 2:
                return 40
            return -10
        
        n3 = 3**n
        # 预处理：每一个 mask 的三进制表示
        mask_span = dict()
        # 预处理：每一个 mask 去除最高位、乘 3、加上新的最低位的结果
        truncate = dict()

        # 预处理
        highest = n3 // 3
        for mask in range(n3):
            mask_tmp = mask
            bits = list()
            for i in range(n):
                bits.append(mask_tmp % 3)
                mask_tmp //= 3
            # 与方法一不同的是，这里需要反过来存储，这样 [0] 对应最高位，[n-1] 对应最低位
            mask_span[mask] = bits[::-1]
            truncate[mask] = [
                mask % highest * 3,
                mask % highest * 3 + 1,
                mask % highest * 3 + 2,
            ]
        
        # dfs(位置，轮廓线上的 mask，剩余的内向人数，剩余的外向人数)
        @lru_cache(None)
        def dfs(pos: int, borderline: int, nx: int, wx: int):
            # 边界条件：如果已经处理完，或者没有人了
            if pos == m * n or nx + wx == 0:
                return 0
            
            x, y = divmod(pos, n)
            
            # 什么都不做
            best = dfs(pos + 1, truncate[borderline][0], nx, wx)
            # 放一个内向的人
            if nx > 0:
                best = max(best, 120 + calc(1, mask_span[borderline][0]) \
                                     + (0 if y == 0 else calc(1, mask_span[borderline][n - 1])) \
                                     + dfs(pos + 1, truncate[borderline][1], nx - 1, wx))
            # 放一个外向的人
            if wx > 0:
                best = max(best, 40 + calc(2, mask_span[borderline][0]) \
                                    + (0 if y == 0 else calc(2, mask_span[borderline][n - 1])) \
                                    + dfs(pos + 1, truncate[borderline][2], nx, wx - 1))

            return best
        
        return dfs(0, 0, nx, wx)

复杂度分析

• 时间复杂度：分为以下部分：

  • 预处理部分计算 $\textit{mask}$ 的三进制表示，$\textit{mask}\backslash0$，$\textit{mask}\backslash1$，$\textit{mask}\backslash2$ 的时间复杂度为 $O(n \cdot 3^n)$；
  • 记忆化搜索部分的状态总数为 $O(m\cdot n\cdot\textit{wx}\cdot\textit{nx}\cdot3^n)$，状态转移时需要枚举 $3=O(1)$ 个状态，转移的时间复杂度为 $O(1)$，总时间复杂度为 $O(m\cdot n\cdot\textit{wx}\cdot\textit{nx}\cdot3^n)$。

  第一项在渐进意义下小于第二项，可以忽略，因此总时间复杂度为 $O(m\cdot n\cdot\textit{wx}\cdot\textit{nx}\cdot3^n)$。

• 空间复杂度：分为以下部分：

  • 预处理部分计算 $\textit{mask}$ 的三进制表示需要的空间为 $O(n \cdot 3^n)$；
  • 预处理部分计算 $\textit{mask}\backslash0$，$\textit{mask}\backslash1$，$\textit{mask}\backslash2$ 需要的空间为 $O(3^n)$；
  • 记忆化搜索部分的状态总数为 $O(m\cdot n\cdot\textit{wx}\cdot\textit{nx}\cdot3^n)$，即为需要的空间。

  第一项和第二项在渐进意义下都小于第三项，可以忽略，因此总空间复杂度写为 $O(m\cdot n\cdot\textit{wx}\cdot\textit{nx}\cdot3^n)$。

统计信息

通过次数	提交次数	AC比率
1390	3339	41.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言