*最大化网格幸福感【LC1659】
给你四个整数
m、n、introvertsCount和extrovertsCount。有一个m x n网格，和两种类型的人：内向的人和外向的人。总共有introvertsCount个内向的人和extrovertsCount个外向的人。请你决定网格中应当居住多少人，并为每个人分配一个网格单元。 注意，不必 让所有人都生活在网格中。
每个人的 幸福感 计算如下：
- 内向的人 开始 时有
120个幸福感，但每存在一个邻居（内向的或外向的）他都会 失去30个幸福感。 - 外向的人 开始 时有
40个幸福感，每存在一个邻居（内向的或外向的）他都会 得到20个幸福感。
邻居是指居住在一个人所在单元的上、下、左、右四个直接相邻的单元中的其他人。
网格幸福感 是每个人幸福感的 总和 。 返回 最大可能的网格幸福感 。
好难 了解一下
状压dp+按行
思路
朴素的dfs会超时，由于每个位置只有「空」「内向」「外向」三种状态，因此可以将这三个状态分别编码为 0,1,2，并用一个长度（位数）为 n 的三进制数对一行的状态进行编码，用状压dp解决。
子问题：如果按行处理的话，枚举每一行的状态得到的最大分数，每一行的分数分为「行内分数」和「行外分数」
- 「行内分数」：在同一行内每个人的分数，内向 120分，外向 40分；以及由于两人相邻（在同一行内，即左右相邻）贡献的额外分数，两个内向 −60分，两个外向 40 分，其余情况 −10分；
「行外分数」：由于两人相邻（在不同行内，即上下相邻）贡献的额外分数，同理为 −60,40,−10分中的一种
- 递归的过程中有四个变量：当前选择的行、前一行的状态码、可供选择的内向的人和外向的人的个数，因此在记忆化需要用四维memo记录
class Solution { private int m; private int mx; private int[] f; private int[][] g;// 记录每个位置的消息 private int[][] bits; private int[] ix; private int[] ex; private Integer[][][][] memo; private final int[][] h = {{0, 0, 0}, {0, -60, -10}, {0, -10, 40}}; public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) { this.m = m; mx = (int) Math.pow(3, n);// 三进制枚举的最大值 f = new int[mx];// 行内分数 g = new int[mx][mx];// 行间分数 bits = new int[mx][n];// mask中第i列的比特值 ix = new int[mx];// mask中内向人的个数 ex = new int[mx];// mask中外向人的个数 memo = new Integer[m][mx][introvertsCount + 1][extrovertsCount + 1]; for (int i = 0; i < mx; ++i) { int mask = i; for (int j = 0; j < n; ++j) { int x = mask % 3;// 状态值 mask /= 3; bits[i][j] = x; if (x == 1) { ix[i]++; f[i] += 120; } else if (x == 2) { ex[i]++; f[i] += 40; } if (j > 0) { f[i] += h[x][bits[i][j - 1]]; } } } for (int i = 0; i < mx; ++i) { for (int j = 0; j < mx; ++j) { for (int k = 0; k < n; ++k) { g[i][j] += h[bits[i][k]][bits[j][k]]; } } } return dfs(0, 0, introvertsCount, extrovertsCount); } private int dfs(int i, int pre, int ic, int ec) { if (i == m || (ic == 0 && ec == 0)) { return 0; } if (memo[i][pre][ic][ec] != null) { return memo[i][pre][ic][ec]; } int ans = 0; for (int cur = 0; cur < mx; ++cur) { if (ix[cur] <= ic && ex[cur] <= ec) { ans = Math.max(ans, f[cur] + g[pre][cur] + dfs(i + 1, cur, ic - ix[cur], ec - ex[cur])); } } return memo[i][pre][ic][ec] = ans; } } 作者：ylb 链接：https://leetcode.cn/problems/maximize-grid-happiness/solutions/2318399/python3javacgotypescript-yi-ti-shuang-ji-fssp/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
