LeetCode 1659 Maximize Grid Happiness 题解：三进制行状态压缩与记忆化搜索（LeetCode-Go 源码剖析）

LeetCode 1659 Maximize Grid Happiness 题解：三进制行状态压缩与记忆化搜索（LeetCode-Go 源码剖析）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇技术指南围绕 LeetCode 第 1659 题「Maximize Grid Happiness（最大化网格幸福感）」展开，完整讲解如何将"内向者/外向者安置在网格中"的组合优化问题，用**三进制行状态压缩 + 记忆化搜索（DFS + DP 表）**转化为可在m, n <= 5规模下高效求解的动态规划问题。读完本文，你将掌握三进制状态编码、行内/行间分数的推导与预计算、四维 DP 状态的设计，以及 LeetCode-Go 仓库中该题的 Go 实现与测试验证方式。

一、题目速览：问题定义、规则与约束

题目给出四个整数：m、n、introvertsCount、extrovertsCount。有一个m x n网格，可以安置两种类型的人：

• 内向者（Introverts）：初始幸福感为120，每存在一个邻居（无论内向还是外向）失去30幸福感；
• 外向者（Extroverts）：初始幸福感为40，每存在一个邻居（无论内向还是外向）获得20幸福感。

邻居是指居住在某个单元上、下、左、右四个直接相邻单元中的其他人。网格幸福感是所有人幸福感的加总，题目要求返回最大可能的网格幸福感。

需要注意的两个关键前提：

• 并不要求所有人都住进网格，可以只安置部分人；
• 约束条件为1 <= m, n <= 5，且0 <= introvertsCount, extrovertsCount <= min(m * n, 6)。

官方示例

示例 1：

Input: m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2 Output: 240

把内向者放在 (1,1)，两个外向者放在 (1,3) 与 (2,3)：

• 内向者 (1,1)：120 - (0 * 30) = 120（0 个邻居）；
• 外向者 (1,3)：40 + (1 * 20) = 60（1 个邻居，即 (2,3)）；
• 外向者 (2,3)：40 + (1 * 20) = 60（1 个邻居，即 (1,3)）。

网格幸福感 =120 + 60 + 60 = 240。

示例 2：

Input: m = 3, n = 1, introvertsCount = 2, extrovertsCount = 1 Output: 260

把两个内向者放在 (1,1) 与 (3,1)，外向者放在 (2,1)：

• 内向者 (1,1)：120 - (1 * 30) = 90（1 个邻居）；
• 外向者 (2,1)：40 + (2 * 20) = 80（2 个邻居）；
• 内向者 (3,1)：120 - (1 * 30) = 90（1 个邻居）。

网格幸福感 =90 + 80 + 90 = 260。

示例 3：

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

上述示例、逐步计算过程与约束均完整继承自 题目文档，仓库 测试用例 中还额外覆盖了一组规模更大的边界输入(5, 5, 6, 6)，期望输出1840。

二、核心难点拆解：三态行编码与四类邻接分数

暴力枚举的规模是灾难性的：每个格子有3 种状态（空白、内向者、外向者），一个m x n网格就有3^(m*n)种摆放方式，在m = n = 5时是不可行的。因此本题必须做状态压缩。

1. 每行一个三进制数

思路是按行处理：每行有n个格子，每个格子 3 种状态，恰好可以用一个n 位三进制数表示整行的状态：

每行状态总量为3^n种。n <= 5时最多3^5 = 243种；仓库实现将表格容量固定为729（即3^6）作为容量上界，实际枚举只进行到int(n3) = 3^n（见 源码实现）。

2. 四类邻接分数的推导

无论横向（行内）还是纵向（行间），任意两个相邻格子的得分贡献只取决于两人的类型组合。设closeScore(x, y)为相邻格子类型x、y的分数贡献：

这正是 源码 中closeScore函数的完整逻辑。整个问题的分数计算，最终都可以归结为"个人初始分"与"上述邻接分数"的叠加。

三、从二维网格到一维行序列：状态压缩的核心思想

把每一行的三进制状态看成一个"行状态"后，m x n的二维网格就退化成了m个行状态组成的一维序列。相邻关系也只剩两类：

• 行内关系：同一行内相邻两列的分数，只取决于该行状态自身；
• 行间关系：上下相邻两行的同列格子的分数，只取决于两个相邻行状态。

这样一来，网格幸福感可以写成：

总幸福感 = Σ(每行的个人初始分 + 每行的行内邻接分) + Σ(相邻两行的行间邻接分)

于是问题转化为：从3^n种行状态中依次选出m个（可少于m行，因为人不一定用完），使得消耗的内向者、外向者人数不超过给定配额，且总幸福感最大。

四、状态设计与转移方程

1. 四维 DP 状态定义

仓库实现定义（见 源码实现）：

dp[lineStatusLast][row][introvertsCount][extrovertsCount]

各维含义：

由于introvertsCount, extrovertsCount <= min(m * n, 6)，人数维度开7个槽位（索引0..6）即可覆盖。

2. 状态转移方程

原文档给出的转移方程如下：

dp[lineStatusLast(row-1)][row][introvertsCount][extrovertsCount] = max{ dp[lineStatusLast(row)][row+1][introvertsCount - countIC(lineStatusLast(row))][extrovertsCount - countEC(lineStatusLast(row))] + scoreInner(lineStatusLast(row)) + scoreOuter(lineStatusLast(row-1), lineStatusLast(row)) }

其中用到了 4 个辅助函数（原文档定义，与源码注释一一对应）：

直观理解：决定"第row行采用哪个行状态"后，消耗掉该行用掉的内向/外向人数，累加上该行的行内分数与它和上一行的行间分数，再递归决定下一行。

五、预计算阶段：把分数全部查表化

转移方程的计算量巨大，因此仓库实现（源码实现）在进入动态规划之前，先把所有行状态相关的统计量与分数一次性算好，转移时直接 O(1) 查表。

1. 三进制展开：lineStatusList

对每个行状态lineStatus，用连续取模/整除把它展开成n位三进制，存入lineStatusList[lineStatus][i]，其中i表示第i列（低位对应第 0 列）：

tmp := lineStatus for i := 0; i < n; i++ { lineStatusList[lineStatus][i] = tmp % 3 tmp /= 3 }

2. 行内分数与人数统计：scoreInner

对每个行状态从左到右扫描每一列：

• 遇1：introvertsCountInner++，个人分加120；
• 遇2：extrovertsCountInner++，个人分加40；
• 与左邻列（i-1）计算closeScore并累加（只向左看，避免重复计算同一条边）。

for i := 0; i < n; i++ { if lineStatusList[lineStatus][i] != 0 { if lineStatusList[lineStatus][i] == 1 { introvertsCountInner[lineStatus]++ scoreInner[lineStatus] += 120 } else if lineStatusList[lineStatus][i] == 2 { extrovertsCountInner[lineStatus]++ scoreInner[lineStatus] += 40 } if i-1 >= 0 { scoreInner[lineStatus] += closeScore(lineStatusList[lineStatus][i], lineStatusList[lineStatus][i-1]) } } }

3. 行间分数：scoreOuter

对任意两行状态lineStatus0、lineStatus1，逐列累加上下同列格子的closeScore：

for i := 0; i < n; i++ { scoreOuter[lineStatus0][lineStatus1] += closeScore(lineStatusList[lineStatus0][i], lineStatusList[lineStatus1][i]) }

六、记忆化搜索实现与边界条件

1. 两个终止条件

dfs函数 的边界条件：

• row == m：所有行已枚举完毕，无论剩余多少人，这一行dp = 0；
• introvertsCount + extrovertsCount == 0：人已经用完了，dp = 0。

这两个条件正好呼应题目"人数可以不用完"的特点——剩余配额即使不为 0，也不再继续摆放。

2. 记忆化判重

dp表在初始化时全部置为-1（即原文档所说"0 行 0 列都初始化为 -1"，实际是整个四维表统一置-1，见 源码实现）：

for i := 0; i < 729; i++ { dp[i] = [6][7][7]int{} for j := 0; j < 6; j++ { dp[i][j] = [7][7]int{} for k := 0; k < 7; k++ { dp[i][j][k] = [7]int{-1, -1, -1, -1, -1, -1, -1} } } }

搜索时若dp[lineStatusLast][row][introvertsCount][extrovertsCount] != -1则直接返回缓存结果，避免重复子问题。

3. 逐行枚举与剪枝

dfs遍历当前行所有n3种行状态，用预计算的introvertsCountInner/extrovertsCountInner做配额剪枝——某行状态需要的人数超过剩余配额则直接跳过：

best := 0 for lineStatus := 0; lineStatus < n3; lineStatus++ { if introvertsCountInner[lineStatus] > introvertsCount || extrovertsCountInner[lineStatus] > extrovertsCount { continue } score := scoreInner[lineStatus] + scoreOuter[lineStatus][lineStatusLast] best = max(best, score+dfs(lineStatus, row+1, introvertsCount-introvertsCountInner[lineStatus], extrovertsCount-extrovertsCountInner[lineStatus], ...)) } dp[lineStatusLast][row][introvertsCount][extrovertsCount] = best return best

入口调用为dfs(0, 0, introvertsCount, extrovertsCount, ...)：第 0 行之前视为"空行"，lineStatusLast = 0表示上一行全空白，因此第一行与"上一行"的行间分数天然为 0，无需特判。

七、完整 Go 实现（仓库原版）

以下是 LeetCode-Go 仓库 中该题的完整解法（与 源码文件 一致）：

package leetcode import ( "math" ) func getMaxGridHappiness(m int, n int, introvertsCount int, extrovertsCount int) int { // lineStatus 将每一行中 3 种状态进行编码，空白 - 0，内向人 - 1，外向人 - 2，每行状态用三进制表示 // lineStatusList[729][6] 每一行的三进制表示 // introvertsCountInner[729] 每一个 lineStatus 包含的内向人数 // extrovertsCountInner[729] 每一个 lineStatus 包含的外向人数 // scoreInner[729] 每一个 lineStatus 包含的行内得分（只统计 lineStatus 本身的得分，不包括它与上一行的） // scoreOuter[729][729] 每一个 lineStatus 包含的行外得分 // dp[上一行的 lineStatus][当前处理到的行][剩余的内向人数][剩余的外向人数] n3, lineStatus, introvertsCountInner, extrovertsCountInner, scoreInner, scoreOuter, lineStatusList, dp := math.Pow(3.0, float64(n)), 0, [729]int{}, [729]int{}, [729]int{}, [729][729]int{}, [729][6]int{}, [729][6][7][7]int{} for i := 0; i < 729; i++ { lineStatusList[i] = [6]int{} } for i := 0; i < 729; i++ { dp[i] = [6][7][7]int{} for j := 0; j < 6; j++ { dp[i][j] = [7][7]int{} for k := 0; k < 7; k++ { dp[i][j][k] = [7]int{-1, -1, -1, -1, -1, -1, -1} } } } // 预处理 for lineStatus = 0; lineStatus < int(n3); lineStatus++ { tmp := lineStatus for i := 0; i < n; i++ { lineStatusList[lineStatus][i] = tmp % 3 tmp /= 3 } introvertsCountInner[lineStatus], extrovertsCountInner[lineStatus], scoreInner[lineStatus] = 0, 0, 0 for i := 0; i < n; i++ { if lineStatusList[lineStatus][i] != 0 { // 个人分数 if lineStatusList[lineStatus][i] == 1 { introvertsCountInner[lineStatus]++ scoreInner[lineStatus] += 120 } else if lineStatusList[lineStatus][i] == 2 { extrovertsCountInner[lineStatus]++ scoreInner[lineStatus] += 40 } // 行内分数 if i-1 >= 0 { scoreInner[lineStatus] += closeScore(lineStatusList[lineStatus][i], lineStatusList[lineStatus][i-1]) } } } } // 行外分数 for lineStatus0 := 0; lineStatus0 < int(n3); lineStatus0++ { for lineStatus1 := 0; lineStatus1 < int(n3); lineStatus1++ { scoreOuter[lineStatus0][lineStatus1] = 0 for i := 0; i < n; i++ { scoreOuter[lineStatus0][lineStatus1] += closeScore(lineStatusList[lineStatus0][i], lineStatusList[lineStatus1][i]) } } } return dfs(0, 0, introvertsCount, extrovertsCount, m, int(n3), &dp, &introvertsCountInner, &extrovertsCountInner, &scoreInner, &scoreOuter) } // 如果 x 和 y 相邻，需要加上的分数 func closeScore(x, y int) int { 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 } // dfs(上一行的 lineStatus，当前处理到的行，剩余的内向人数，剩余的外向人数） func dfs(lineStatusLast, row, introvertsCount, extrovertsCount, m, n3 int, dp *[729][6][7][7]int, introvertsCountInner, extrovertsCountInner, scoreInner *[729]int, scoreOuter *[729][729]int) int { // 边界条件：如果已经处理完，或者没有人了 if row == m || introvertsCount+extrovertsCount == 0 { return 0 } // 记忆化 if dp[lineStatusLast][row][introvertsCount][extrovertsCount] != -1 { return dp[lineStatusLast][row][introvertsCount][extrovertsCount] } best := 0 for lineStatus := 0; lineStatus < n3; lineStatus++ { if introvertsCountInner[lineStatus] > introvertsCount || extrovertsCountInner[lineStatus] > extrovertsCount { continue } score := scoreInner[lineStatus] + scoreOuter[lineStatus][lineStatusLast] best = max(best, score+dfs(lineStatus, row+1, introvertsCount-introvertsCountInner[lineStatus], extrovertsCount-extrovertsCountInner[lineStatus], m, n3, dp, introvertsCountInner, extrovertsCountInner, scoreInner, scoreOuter)) } dp[lineStatusLast][row][introvertsCount][extrovertsCount] = best return best } func max(a int, b int) int { if a > b { return a } return b }

几点实现细节值得注意：

• scoreOuter[lineStatus][lineStatusLast]传入的是当前行与上一行，与函数参数顺序一致，读代码时不要与"当前行作为第二参数"混淆；
• dfs返回 0 的两个分支分别对应"行已枚举完"与"人数已耗尽"，剩余配额不需要用尽，天然支持题目"不必让所有人都生活在网格中"的设定；
• 各预计算表与dp表通过指针传入dfs，避免深拷贝开销。

八、测试用例与验证方式

仓库为本题提供了表驱动测试（见 测试文件），覆盖 4 组输入：

前 3 组即题目官方示例；第 4 组(5, 5, 6, 6)是测试文件额外补充的最大规模输入，用于验证算法在m, n与人数配额同时取上限时仍能给出正确结果。测试结构为question1659{ para1659{...}, ans1659{...} }的表驱动风格，Test_Problem1659依次打印每组输入与getMaxGridHappiness的实际输出，可直接用 Go 测试框架运行验证。仓库根目录的 gotest.sh 展示了本项目统一的质量验证方式：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

即对./leetcode/...下所有包执行带覆盖率采集的测试，本解法所在的leetcode包也包含在其中。

九、复杂度分析

从源码结构可以推断本解法的复杂度特征：

• DP 状态数：3^n（上一行状态数）×m（行数）×(introvertsCount + 1)×(extrovertsCount + 1)。在约束n <= 5、人数上限 6 时，状态总数约为243 × 5 × 7 × 7，规模很小；
• 单状态转移：需要枚举3^n种当前行状态并查表，每次转移为 O(1)；
• 预计算开销：scoreInner为3^n × n，scoreOuter为(3^n)² × n，同样在约束下完全可承受。

整体思路可以概括为：用三进制压缩行状态、用预计算消除重复分数计算、用记忆化 DFS 剪掉重复子问题，把指数级的格子摆放问题收敛到"行级"的动态规划上，这正是本题从"不可枚举"到"可求解"的关键。

十、小结

本解法是一个"状态压缩 + 记忆化搜索"的典型范本：

1. 编码层：用三进制数编码每行三态，把二维网格压成一维行序列；
2. 规则层：通过closeScore把"内向减 30、外向加 20"的计分规则收敛为四类邻接分值（-60 / +40 / -10 / 0）；
3. 优化层：countIC、countEC、scoreInner、scoreOuter全部预计算成表，dp[729][6][7][7]记忆化复用子问题结果；
4. 边界层：row == m与人数耗尽两个终止条件，配合-1初始化完成记忆化判重。

读者可将本文与仓库中的 题目文档、源码实现 及 测试用例 对照阅读，在理解状态转移方程的基础上，把同一套"三进制状态压缩 + 查表 + 记忆化"方法论迁移到其他网格类组合优化问题上。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go