写在前面

周赛最后一题，想到dp了，但是状态表示和转移死活想不出来，最后参考零神的题解，总算是自己敲出来了，零神题解讲解的很清楚，我就不在过多解释了，这里只附上题目及代码。

题目

代码

class Solution {

    int n;
    int m;
    int n3;

    int[][] maskTrans;//对每一种状态mask转换为3进制
    int[] inMask;//状态mask内向的人数
    int[] exMask;//状态mask外向的人数
    int[] scoreInner;//状态mask对应的行内分数
    int[][] scoreOuter;//状态mask1和mask2两者行间的分数

    int[][][][] memo;//备忘录

    public int getMaxGridHappiness(int m, int n, int in, int ex) {
        //初始化变量
        this.n = n;
        this.m = m;
        this.n3 = (int)Math.pow(3, n);
        
        //初始化数组
        this.maskTrans = new int[n3][n];
        this.inMask = new int[n3];
        this.exMask = new int[n3];
        this.scoreInner = new int[n3];
        this.scoreOuter = new int[n3][n3];
        this.memo = new int[n3][m][in + 1][ex + 1];
        for(int mask = 0; mask < n3; mask++){
            for(int i = 0; i < m; i++){
                for(int j = 0; j <= in; j++){
                    for(int k = 0; k <= ex; k++){
                        memo[mask][i][j][k] = -1;
                    }
                }
            }
        }

        //预处理
        // mask状态与3进制转换
        for(int mask = 0; mask < n3; mask++){
            int tmp = mask;
            for(int i = 0; i < n; i++){
                maskTrans[mask][i] = tmp % 3;
                tmp /= 3;
            }
        }
        
        // mask状态对应的内向外向人数、及行内分数
        for(int mask = 0; mask < n3; mask++){
            for(int i = 0; i < n; i++){
                if(maskTrans[mask][i] == 1){
                    //内向
                    inMask[mask]++;
                    scoreInner[mask] += 120;
                }else if(maskTrans[mask][i] == 2){
                    //外向
                    exMask[mask]++;
                    scoreInner[mask] += 40;
                }else{
                    continue;
                }

                //前一个放置了内向或者外向的人
                if(i > 0 && maskTrans[mask][i - 1] != 0){
                    scoreInner[mask] += compute(maskTrans[mask][i], maskTrans[mask][i - 1]);
                }
            }
        }

        // mask1 和 mask2 的行间分数
        for(int mask1 = 0; mask1 < n3; mask1++){
            for(int mask2 = 0; mask2 < n3; mask2++){
                for(int i = 0; i < n; i++){
                    //上下两个人相邻
                    if(maskTrans[mask1][i] != 0 && maskTrans[mask2][i] != 0){
                        scoreOuter[mask1][mask2] += compute(maskTrans[mask1][i], maskTrans[mask2][i]);
                    }
                }
            }
        }

        return dfs(0, 0, in, ex);

    }

    /**
     * 计算人物 p1 和 p2 对行内分数的贡献
     */
    public int compute(int p1, int p2){
        if(p1 == 1 && p2 == 1){
            return -60;
        }
        if(p1 == 2 && p2 == 2){
            return 40;
        }
        return -10;
    }

    /**
     * 上一行为maskLast状态
     * 当前为第row行
     * 还剩下in个内向的人
     * 还剩下ex个外向的人
     * 返回这种情况下最大可能的网格幸福感
     */
    public int dfs(int maskLast, int row, int in, int ex){
        if(row == m || in == 0 && ex == 0){
            return 0;
        }
        //记忆化
        if(memo[maskLast][row][in][ex] != -1){
            return memo[maskLast][row][in][ex];
        }

        int res = 0;
        for(int mask = 0; mask < n3; mask++){
            if(inMask[mask] > in || exMask[mask] > ex)
                continue;
            res = Math.max(res, scoreInner[mask] + scoreOuter[maskLast][mask] + dfs(mask, row + 1, in - inMask[mask], ex - exMask[mask]));
        }
        return memo[maskLast][row][in][ex] = res;
    }
}

还是第一次遇到3进制的状压DP，也算是学到了些新东西了
如果文章有写的不对的地方还请指出，感恩相遇~