作者：whisper

链接：http://proprogrammar.com:443/article/607

声明：请尊重原作者的劳动，如需转载请注明出处

    题目如下

    第一次做的时候并不会，然后看评论说用状态压缩dp做，也不会状态压缩dp，所以就没有做。这两天看了一下状态压缩dp，夜里有时间试着做了一下，花了大半夜时间终于做出来了，如果会状态压缩dp的话应该是不太难的，我是在下面的地址学习的状态压缩dp：状态压缩动态规划 状压DP

    先讲一下思路，从第一行开始一行一行处理，第一行和最后一行比较特殊，只和第二行和倒数第二行有关，其它行与上下两行有关，而且还涉及到可用数量，我们用一位0，1表示力和扣，我们用一个四维dp来处理dp[i][j][k][m]，i是行数，j是当前行状态（0，1序列），k是上一行状态，m是当前扣的数量（我们不妨处理扣），代码如下：

    long redPacket2020(int row, int col) {
		long[][][][] dp = new long[row+1][1<<col][1<<col][row * col / 2 + 1];
		long res = 0;
		int[] cost = new int[1<<col];
		int temp;
		
        // 当前状态扣（1）的数量
		for(int i = 0; i < 1<<col; i++) {
			temp = i;
			while(temp != 0) {
				if(temp % 2 == 1) {
					cost[i]++;
				}
				temp /= 2;
			}
			//dp[1][i][0][cost[i]] = 1;
		}
		
        // 预处理第二行：当确定第二行状态时，第一行的可能状态，两者组成dp[2][i][j][cost[i] + cost[j]]
		for(int i = 0; i < 1<<col; i++) {
			for(int j = 0; j < 1<<col; j++) {
				if(validStatus(col, new int[] {j, i})) {
					dp[2][i][j][cost[i] + cost[j]] = 1;
				}
			}
		}
		
        // 从第三行开始，确定该行每一个状态与上一行可能状态构成的组合数，上一行的状态与上上一行有关
        // 即要确定前一行，前一行与上上一行和当前行有关，在validStatus中计算三行状态是否相容
		for(int i = 3; i <= row; i++) {
			for(int j = 0; j < 1<<col; j++) {//当前行状态
				for(int m = 0; m < 1<<col; m++) {//上一行状态
					for(int n = 0; n < 1<<col; n++) {//上上行状态
						if(validStatus(col, new int[] {m, j, n})) {
                            // 还要考虑使用的扣（1）的数量
							for(int c = col * row / 2; c >= cost[j]; c--) {
								dp[i][j][m][c] += dp[i - 1][m][n][c - cost[j]];
							}
						}
					}
				}
			}
		}
		
        // 我们上面每次确定的是前一行，所以最后一行还没确定，最后一行只与倒数第二行有关
		for(int i = 0; i < 1<<col; i++) {//最后一行状态
			for(int j = 0; j < 1<<col; j++) {//倒数第二行状态
				if(validStatus(col, new int[] {i, j})) {
					res += dp[row][i][j][row * col / 2];//取用了30个扣的
				}
			}
		}
		
		return res;
	}
	
    // 取数的二进制数组，即力，扣的排列，一行的状态
	private int[] bitArray(int num, int len) {
		int[] res = new int[len];
		for(int i = 0; i < len; i++) {
			res[i] = num % 2;
			num /= 2;
		}
		return res;
	}
	
	// 如果竖的三个相同，两边横的也对应相同，返回false
	// 如果竖的两个相同，两边横的也对应相同，返回false
	// 否则返回true
	// 分1和0两种情况，注意处理第一行与最后一行
	private boolean validStatus(int col, int... row) {
		int[] bitArr = bitArray(row[0], col);
		int and = row[0], or = row[0], index, temp;
		for(int i = 1; i < row.length; i++) {
			and &= row[i];
			or |= row[i];
		}
		if(and > 0) {
			index = 0;
			while(index < col && and > 0) {
				temp = and % 2;
				if(temp == 1) {
					if(index == 0) {
						if(bitArr[index + 1] == 1) {
							return false;
						}
					}else if(index == col - 1) {
						if(bitArr[index - 1] == 1) {
							return false;
						}
					}else {
						if(bitArr[index + 1] == 1 && bitArr[index - 1] == 1) {
							return false;
						}
					}
				}
				and /= 2;
				index++;
			}
		}
		
		index = 0;
		while(index < col) {
			temp = or % 2;
			if(temp == 0) {
				if(index == 0) {
					if(bitArr[index + 1] == 0) {
						return false;
					}
				}else if(index == col - 1) {
					if(bitArr[index - 1] == 0) {
						return false;
					}
				}else {
					if(bitArr[index + 1] == 0 && bitArr[index - 1] == 0) {
						return false;
					}
				}
			}
			or /= 2;
			index++;
		}
		
		return true;
	}

    算法解释在注释里，对于题目中的10行6列，结果是1174753962370370，第一次写状态压缩dp，想了很久，也不会优化，但思路是清楚的，有两点技巧要注意一下，就是dp的维数问题，第一维是行dp[i]，当前行与其它几行有关，就多几维，因为当前行与上下两行有关，所以会多两维表示两行的状态dp[i][j][k]，如果限定数量，那么还要加一维表示数量dp[i][j][k][m]

亲爱的读者：有时间可以点赞评论一下