通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

leetcode-2020新年红包题4-灯笼排列

905人浏览 / 0人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  /  leetcode  | 

作者:因情语写

链接:https://proprogrammar.com/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]


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

点赞(72) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告