题目链接：https://leetcode.cn/problems/maximize-grid-happiness/

题目大意：给出一个网格m*n，里面可以放内向的人、放外向的人或者什么也不放。每个内向人或者外向人放了以后有加分。但内向人周围有人时会减分，外向人周围有人时会加分。共有ic个内向人和ec个外向人（可以不放完）。求使得分数最大的放置方法。

思路：开始时以为这是像背包问题那样的NPC问题，感觉没有头绪。后来才知道这种问题一般都是DP。

首先注意到【周围】的定义，只是上下左右四个地方。那么在DP放置时，某一个位置只受其前n个格子放置情况的影响（这n个格子，第一个就是当前位置的上方，最后一个就是当前位置的左方）。

那么定义dp[pos][intro][extro][status]为【在考虑pos位置放什么时】【剩余intro个内向人和extra个外向人】【前n个格子状态为status】的最大分数。

其中，pos是网格的下标，将二维的网格线性化成一维。

status用三进制表示，n个格子，不放是0，放内向是1，放外向是2。那么【上方】== status / 3^(n-1)，【左方】== status % 3。每一次移动一个格子，status就要忘记第一个位，添加新一个位，也就是三进制左移一位，并加上当前格子的放置情况（0/1/2）。

所有【当前位置】与【上方/左方】的相互影响分数提前在一个矩阵interact[][]里记好。注意，至于右方/下方的影响，是由下一行的放置时再来计算的。

DP的转移

                for (int status = 0; status < status_max; status++) {int status_new = (status*3) % status_max;// set 0dp[pos][intro][extro][status] = max(dp[pos][intro][extro][status], dp[pos+1][intro][extro][status_new]);// set 1if (intro > 0) {int diff = 120 + (y != 0) * interact[1][status%3] + interact[1][status/status_max1];dp[pos][intro][extro][status] = max(dp[pos][intro][extro][status], diff + dp[pos+1][intro-1][extro][status_new+1]);}//set 2if (extro > 0) {int diff = 40 + (y != 0) * interact[2][status%3] + interact[2][status/status_max1];dp[pos][intro][extro][status] = max(dp[pos][intro][extro][status], diff + dp[pos+1][intro][extro-1][status_new+2]);}}

当然，至于结果为什么是dp[0][ic][ec][0]，还有为什么是那么几层循环，我还没有搞清楚，待补。

完整代码

class Solution {
public:int getMaxGridHappiness(int m, int n, int ic, int ec) {int interact[3][3] = {0, 0, 0, 0, -60, -10, 0, -10, 40};int status_max = pow(3, n);int status_max1 = pow(3, n-1);const int mn = m * n;int dp[mn+1][ic+1][ec+1][status_max];memset(dp, 0, sizeof(dp));for (int pos = mn-1; pos >= 0; pos--) {int x = pos / n, y = pos % n;for (int intro = 0; intro <= ic; intro++) {for (int extro = 0; extro <= ec; extro++) {for (int status = 0; status < status_max; status++) {int status_new = (status*3) % status_max;// set 0dp[pos][intro][extro][status] = max(dp[pos][intro][extro][status], dp[pos+1][intro][extro][status_new]);// set 1if (intro > 0) {int diff = 120 + (y != 0) * interact[1][status%3] + interact[1][status/status_max1];dp[pos][intro][extro][status] = max(dp[pos][intro][extro][status], diff + dp[pos+1][intro-1][extro][status_new+1]);}// set 2if (extro > 0) {int diff = 40 + (y != 0) * interact[2][status%3] + interact[2][status/status_max1];dp[pos][intro][extro][status] = max(dp[pos][intro][extro][status], diff + dp[pos+1][intro][extro-1][status_new+2]);}}}}}return dp[0][ic][ec][0];}
};