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
示例 3：
输入：m = 2, n = 2, introvertsCount = 4, extrovertsCount = 0
输出：240
提示：
1 <= m, n <= 50 <= introvertsCount, extrovertsCount <= min(m * n, 6)
解题思路
解题思路
这是一道复杂的动态规划题，需要使用状态压缩和记忆化搜索。
核心思路：
状态设计：由于网格较小(最大5x5)，我们可以逐行处理。对于每一行，我们需要记录：
- 当前处理到的位置(row, col)
- 剩余的内向者和外向者数量
- 上一行的状态(用三进制数表示：0=空，1=内向者，2=外向者)
状态转移：对于每个位置，我们有3种选择：
- 放置内向者(如果还有剩余)
- 放置外向者(如果还有剩余)
- 保持空白
幸福值计算：
- 内向者：120 - 30 × 邻居数
- 外向者：40 + 20 × 邻居数
- 需要考虑与左边和上边邻居的互相影响
优化技巧：
- 使用记忆化避免重复计算
- 用三进制数压缩行状态
- 预计算邻居贡献值
时间复杂度分析：状态数约为 O(3^n × m × n × C1 × C2)，其中C1、C2是人数上限。由于约束条件较小，实际运行效率可接受。
代码实现
class Solution {
public:
int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
// 记忆化搜索
unordered_map<string, int> memo;
function<int(int, int, int, int, int)> dfs = [&](int pos, int mask, int ic, int ec, int prevMask) -> int {
if (pos == m * n) return 0;
if (ic < 0 || ec < 0) return -1e9;
string key = to_string(pos) + "," + to_string(mask) + "," + to_string(ic) + "," + to_string(ec);
if (memo.count(key)) return memo[key];
int row = pos / n, col = pos % n;
int res = 0;
// 三种选择：空、内向者、外向者
for (int choice = 0; choice <= 2; choice++) {
if (choice == 1 && ic == 0) continue;
if (choice == 2 && ec == 0) continue;
int happiness = 0;
int neighbors = 0;
// 计算邻居数和幸福值
if (choice > 0) {
// 检查左邻居
if (col > 0) {
int left = (mask >> ((n-1) * 2)) & 3;
if (left > 0) {
neighbors++;
if (choice == 1) happiness -= 30; // 内向者失去幸福
else happiness += 20; // 外向者获得幸福
// 邻居也受影响
if (left == 1) happiness -= 30; // 左邻居是内向者
else happiness += 20; // 左邻居是外向者
}
}
// 检查上邻居
if (row > 0) {
int up = prevMask & 3;
if (up > 0) {
neighbors++;
if (choice == 1) happiness -= 30;
else happiness += 20;
if (up == 1) happiness -= 30;
else happiness += 20;
}
}
// 基础幸福值
if (choice == 1) happiness += 120; // 内向者
else happiness += 40; // 外向者
}
// 更新状态
int newMask = (mask >> 2) | (choice << ((n-1) * 2));
int newPrevMask = (row == 0) ? 0 : (prevMask >> 2);
if (col == 0 && row > 0) {
newPrevMask = mask & ((1 << (n * 2)) - 1);
}
int newIc = ic - (choice == 1 ? 1 : 0);
int newEc = ec - (choice == 2 ? 1 : 0);
res = max(res, happiness + dfs(pos + 1, newMask, newIc, newEc,
(col == n-1) ? newMask : prevMask));
}
return memo[key] = res;
};
return dfs(0, 0, introvertsCount, extrovertsCount, 0);
}
};
class Solution:
def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:
from functools import lru_cache
@lru_cache(None)
def dfs(pos, prevRow, ic, ec):
if pos == m * n:
return 0
if ic < 0 or ec < 0:
return float('-inf')
row, col = pos // n, pos % n
maxHappiness = 0
# 三种选择：0=空，1=内向者，2=外向者
for choice in range(3):
if choice == 1 and ic == 0:
continue
if choice == 2 and ec == 0:
continue
happiness = 0
if choice > 0:
# 基础幸福值
if choice == 1: # 内向者
happiness += 120
else: # 外向者
happiness += 40
# 检查左邻居
if col > 0:
left = (prevRow >> (2 * (col - 1))) & 3
if left > 0:
if choice == 1: # 当前是内向者
happiness -= 30
else: # 当前是外向者
happiness += 20
# 左邻居受影响
if left == 1: # 左邻居是内向者
happiness -= 30
else: # 左邻居是外向者
happiness += 20
# 检查上邻居
if row > 0:
up = (prevRow >> (2 * col)) & 3
if up > 0:
if choice == 1: # 当前是内向者
happiness -= 30
else: # 当前是外向者
happiness += 20
# 上邻居受影响
if up == 1: # 上邻居是内向者
happiness -= 30
else: # 上邻居是外向者
happiness += 20
# 更新状态
newPrevRow = (prevRow & ((1 << (2 * col)) - 1)) | (choice << (2 * col))
newIc = ic - (1 if choice == 1 else 0)
newEc = ec - (1 if choice == 2 else 0)
nextPrevRow = prevRow if col < n - 1 else newPrevRow
maxHappiness = max(maxHappiness,
happiness + dfs(pos + 1, nextPrevRow, newIc, newEc))
return maxHappiness
return dfs(0, 0, introvertsCount, extrovertsCount)
public class Solution {
private Dictionary<string, int> memo = new Dictionary<string, int>();
public int GetMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
return DFS(0, 0, m, n, introvertsCount, extrovertsCount);
}
private int DFS(int pos, int prevRow, int m, int n, int ic, int ec) {
if (pos == m * n) return 0;
if (ic < 0 || ec < 0) return int.MinValue / 2;
string key = $"{pos},{prevRow},{ic},{ec}";
if (memo.ContainsKey(key)) return memo[key];
int row = pos / n, col = pos % n;
int maxHappiness = 0;
// 三种选择：0=空，1=内向者，2=外向者
for (int choice = 0; choice <= 2; choice++) {
if (choice == 1 && ic == 0) continue;
if (choice == 2 && ec == 0) continue;
int happiness = 0;
if (choice > 0) {
// 基础幸福值
happiness += choice == 1 ? 120 : 40;
// 检查左邻居
if (col > 0) {
int left = (prevRow >> (2 * (col - 1))) & 3;
if (left > 0) {
happiness += choice == 1 ? -30 : 20;
happiness += left == 1 ? -30 : 20;
}
}
// 检查上邻居
if (row > 0) {
int up = (prevRow >> (2 * col)) & 3;
if (up > 0) {
happiness += choice == 1 ? -30 : 20;
happiness += up == 1 ? -30 : 20;
}
}
}
// 更新状态
int newPrevRow = (prevRow & ((1 << (2 * col)) - 1)) | (choice << (2 * col));
int newIc = ic - (choice == 1 ? 1 : 0);
int newEc = ec - (choice == 2 ? 1 : 0);
int nextPrevRow = col < n - 1 ? prevRow : newPrevRow;
maxHappiness = Math.Max(maxHappiness,
happiness + DFS(pos + 1, nextPrevRow, m, n, newIc, newEc));
}
return memo[key] = maxHappiness;
}
}
var getMaxGridHappiness = function(m, n, introvertsCount, extrovertsCount) {
const memo = new Map();
function dp(pos, mask, introverts, extroverts) {
if (pos === m * n) return 0;
const key = `${pos},${mask},${introverts},${extroverts}`;
if (memo.has(key)) return memo.get(key);
const row = Math.floor(pos / n);
const col = pos % n;
// Option 1: place nothing
let result = dp(pos + 1, mask >> 1, introverts, extroverts);
// Option 2: place introvert
if (introverts > 0) {
let happiness = 120;
let neighbors = 0;
// Check left neighbor
if (col > 0 && (mask & 1)) {
neighbors++;
}
// Check top neighbor
if (row > 0 && (mask & (1 << (n - 1)))) {
neighbors++;
}
happiness -= neighbors * 30;
// Add happiness from neighbors
if (col > 0 && (mask & 1)) {
const leftType = (mask & 2) ? 40 : -30; // extrovert gains, introvert loses
happiness += leftType;
}
if (row > 0 && (mask & (1 << (n - 1)))) {
const topType = (mask & (1 << n)) ? 40 : -30;
happiness += topType;
}
const newMask = (mask >> 1) | (1 << (n - 1));
result = Math.max(result, happiness + dp(pos + 1, newMask, introverts - 1, extroverts));
}
// Option 3: place extrovert
if (extroverts > 0) {
let happiness = 40;
let neighbors = 0;
// Check left neighbor
if (col > 0 && (mask & 1)) {
neighbors++;
}
// Check top neighbor
if (row > 0 && (mask & (1 << (n - 1)))) {
neighbors++;
}
happiness += neighbors * 20;
// Add happiness from neighbors
if (col > 0 && (mask & 1)) {
const leftType = (mask & 2) ? 20 : -30; // extrovert gains, introvert loses
happiness += leftType;
}
if (row > 0 && (mask & (1 << (n - 1)))) {
const topType = (mask & (1 << n)) ? 20 : -30;
happiness += topType;
}
const newMask = (mask >> 1) | (1 << (n - 1)) | (1 << n);
result = Math.max(result, happiness + dp(pos + 1, newMask, introverts, extroverts - 1));
}
memo.set(key, result);
return result;
}
return dp(0, 0, introvertsCount, extrovertsCount);
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(3^n × m × n × C₁ × C₂)，其中 C₁、C₂ 分别是内向者和外向者的数量上限。由于约束条件 m,n ≤ 5，实际状态数较少 |
| 空间复杂度 | O(3^n × m × n × C₁ × C₂)，主要用于记忆化存储和递归调用栈 |