【算法】Maximize Grid Happiness 最大化网格幸福感动态规划

这篇具有很好参考价值的文章主要介绍了【算法】Maximize Grid Happiness 最大化网格幸福感动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Maximize Grid Happiness 最大化网格幸福感

问题描述：

给你四个整数 m、n、introvertsCount 和 extrovertsCount 。有一个 m x n 网格，和两种类型的人：内向的人和外向的人。总共有 introvertsCount 个内向的人和 extrovertsCount 个外向的人。

请你决定网格中应当居住多少人，并为每个人分配一个网格单元。注意，不必让所有人都生活在网格中。

每个人的幸福感计算如下：

内向的人开始时有 120 个幸福感，但每存在一个邻居（内向的或外向的）他都会失去 30 个幸福感。
外向的人开始时有 40 个幸福感，每存在一个邻居（内向的或外向的）他都会得到 20 个幸福感。
邻居是指居住在一个人所在单元的上、下、左、右四个直接相邻的单元中的其他人。

网格幸福感是每个人幸福感的总和。返回最大可能的网格幸福感。

n,m 范围[1,5] ,introvertsCount, extrovertsCount 范围[0,min(m * n, 6)]

分析

动态规划还是基于上一版本的DFS自底向上做的递推。
时间复杂度与空间复杂度和之前的DFS属于同一等级。状态转移方程参考以下:

$\max ( f[i][in-curin][ex-curex][prestate] + score[state][prestate])\\ curin 当前i行intro的人数、 curex 当前i行extro的人数\\ score[i][j] 当前行状态i与上一行状态j的影响产生的得分$

代码

class Solution {
    static final int T = 243, N = 5, M = 6;
    int n, m, tot;
    int[][] maskBits;
    int[] ivCount;
    int[] evCount;
    int[] innerScore;
    int[][] interScore;
    int[][][][] d;
    // 邻居间的分数
    static int[][] score = {
        {0, 0, 0},
        {0, -60, -10},
        {0, -10, 40}
    };
     
    public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
        this.n = n;
        this.m = m;
        // 状态总数为 3^n
        this.tot = (int) Math.pow(3, n);
        this.maskBits = new int[T][N];
        this.ivCount = new int[T];
        this.evCount = new int[T];
        this.innerScore = new int[T];
        this.interScore = new int[T][T];
        int[][][][] f = new int[N+1][M + 1][M + 1][T];
		this.d = new int[N][T][M + 1][M + 1];
		int excount =extrovertsCount;
		int incount =introvertsCount;
        int ans =0;
		initData();
		for (int i = 0; i <= m; i++) {
			for (int in = 0; in <= incount; in++) {
                for (int ex = 0; ex <= excount; ex++) {
					Arrays.fill(f[i][in][ex], -1);
				}
            }
        }
		f[0][0][0][0] = 0;
        for (int i = 1; i <= m; i++) {
			for (int in = 0; in <= incount; in++) {
                for (int ex = 0; ex <= excount; ex++) {
					for (int state = 0; state < T; state++) {
						int curin = ivCount[state];
						if(in<curin) continue;
						int curex = evCount[state];
						if(ex<curex) continue; 
						int prein = in-curin;
						int preex = ex-curex;
						for (int prestate = 0; prestate < T; prestate++) {
							if (f[i-1][prein][preex][prestate]==-1){
								continue;
							}		
							int v = innerScore[state];
							v+=interScore[prestate][state];
							f[i][in][ex][state]=Math.max(f[i][in][ex][state],f[i-1][prein][preex][prestate]+v); 
						}
						if (i==m) ans = Math.max(ans, f[i][in][ex][state]); 
					
					} 
				} 
            }
        }
        return ans;
    }

    public void initData() {
        // 计算行内分数
        for (int mask = 0; mask < tot; mask++) {
            int maskTmp = mask;
            for (int i = 0; i < n; i++) {
                int x = maskTmp % 3;
                maskBits[mask][i] = x;
                maskTmp /= 3;
                if (x == 1) {
                    ivCount[mask]++;
                    innerScore[mask] += 120;
                } else if (x == 2) {
                    evCount[mask]++;
                    innerScore[mask] += 40;
                }
                if (i > 0) {
                    innerScore[mask] += score[x][maskBits[mask][i - 1]];
                }
            }
        }
        // 计算行间分数
        for (int i = 0; i < tot; i++) {
            for (int j = 0; j < tot; j++) {
                interScore[i][j] = 0;
                for (int k = 0; k < n; k++) {
                    interScore[i][j] += score[maskBits[i][k]][maskBits[j][k]];
                }
            }
        }
    }
	 
}