[LeetCode]Zuma Game

第一反应是尝试用DP做，比如对于当前board，我们可以进行状态压缩，其可以变成类似2W3R4B的string。我们用dp[state]表示在board处于state状态下将其消去需要的最小球数，那么对于board，如果其状态为i，假设对于一个input ball，其可以插入任何两个char之间使board状态变为j(如果有消去board变短，否则变长)，我们可以得到递推公式dp[i] = min(1 + dp[j]) j代表所有apply 当前ball之后可能达到的状态。如果我们遍历所有在手上的ball，并且枚举所有apply ball之后的状态，我们可以求得dp公式。我们用dp[i]表示处在i状态的board，消去board所需要的最小ball的数量，我们可以有递推公式：

• dp[i] = min(1 + dp[j]), j代表apply R/B/W/G/Y之后所有可能的状态

这里要注意的一点是，如果我们仅仅用dp[i]来表示子问题，这个子问题不是互相独立的，因为dp[i]的值取决于当前我们手上剩余的球的情况，对于同样的状态i，如果我们手上剩余的球不同，那么dp[i]的值显然不同。也就是说，我们的每次决策是有后效性的，我们不能仅仅用dp[i]来表示子问题。那么我们应该用的是二维矩阵，dp[i][j]代表处于状态i的board，和我们手上剩余球的状态为j的情况下，消去board所需要的最小ball的数量。这个子问题是独立的，因为在给定i和j的条件下，dp[i][j]的值是确定的。递推方程为：

• dp[i][j] = min(1 + dp[x][y]), x，y分别代表每次枚举手上的球，apply到board之后，board的状态和手上剩余球的状态

此外值得注意的一点是，我们不需要在每一个位置插入，因为显然我们只需要消去相同颜色的球，我们只需要统计对应颜色的区间，然后看是否可以消去。比如"RRWWB"，和球"R"，我们只需要在apply"RR"的连续区间消去他们即可，不需要遍历其他的位置。而且每一次可以apply多个球，如果我们手上有足够的球，对于board中单独颜色的球，我们完全可以apply两个凑齐三个同样颜色的球从而消去。比如"WRW"，和球''RR"，我们加上两个R凑齐三个消去，而不需要第一次apply一个R，之后再apply第二个。所以我们只需要统计手上每个颜色的球有多少个。

另外值得注意的几点：

1. 每一个消去区间之后，可能board会出现需要merge的情况，比如"WRRWW"，手上的球为"R"，状态压缩之后的board为1W2R2W，apply "R"消去中间的R之后，board会变为1W2W，这时候我们需要将其merge为3W
2. 不要提前消去大于3的区间，比如"WRRWWW"和"R"，最左边的W需要消去R之后和右边的三个merge在一起之后变为4W消去。我们只在apply ball的时候消去区间。
3. 那么在2的情况下，有的颜色，我们手上没有，那么该怎么办呢？很简单，我们假设每时每刻我们手上都有五种颜色的球，只不过其数量可以为0个。这样当这种情况出现的时候，我们仍然可以apply 0个W从而消去4W

这样的话我们的递推公式又可以变为：

• dp[i][j] = min(1 + dp[x][y]), x，y分别代表每次apply 0/1/2个R/B/W/G/Y，并且可以消去一个区间的情况下，board的状态和手上剩余球的状态

鉴于board状态和手上球的状态只能用string表示，所以用recursion + memorization的写法是最好的。这里我没有用memorization，直接用的递归，AC也是没有问题的。时间复杂度最坏O(n ^ n)，n为board的长度，因为最坏的情况在当前状态下我们每次只能消去一个球，而且我们需要遍历消去每一个球的可能性。但是大部分情况下是ok的，因为很多可能性都被我们剪枝剪掉了。代码如下：

	class Solution {
	public:
	int findMinStep(string board, string hand) {
	string boardC = compress(board);
	string chars = "RYBGW";
	unordered_map<char, int> map;
	//still count when there is no sunch color in hand
	//since if we eventually have consecutive colors with length
	//longer than 3 we can remove it
	//for example, RWWRRRRRR, we don't want to remove right Rs first
	//but we can remove Rs enventually after we remove Ws
	for(char c: chars)map[c] = 0;
	for(char c : hand)++map[c];
	return applyHand(boardC, map);
	}
	private:
	string compress(string input)
	{
	input += "$";
	string abbr = "";
	int cnt = 0;
	for(int i = 0; i < input.size(); ++i)
	{
	if((!i || input[i] == input[i - 1]) && input[i] != '$')++cnt;
	else
	{
	abbr += to_string(cnt) + string(1, input[i - 1]);
	cnt = 1;
	}
	}
	return abbr;
	}
	//merge if necessary, for example 1W2R1W will become 1W1W after we apply R
	//we need to merge it to be 2W, but don't get rid of consecutive colors here
	//since for example board "RBBRRRRRR" hand "B", if we delete suffix RRRRRR first
	//then we can never remove sigle prepending R anymore, always remove while applying
	//colors
	void merge(string& s1, const string& s2)
	{
	if(s1.empty()){s1 = s2;return;}
	if(s2.empty())return;
	int j = 0;
	while(isdigit(s2[j]))++j;
	int num = stoi(s2.substr(0, j));
	char color = s2[j];
	if(s1.back() != color)
	s1 += s2;
	else
	{
	int len = s1.size(), i = len - 2;
	while(i >= 0 && isdigit(s1[i]))--i;
	int prevNum = stoi(s1.substr(i + 1, len - 2 - i));
	num += prevNum;
	s1 = s1.substr(0, i + 1) + to_string(num) + string(1, color) + s2.substr(j + 1);
	}
	}
	int applyHand(string& board, unordered_map<char, int>& hand)
	{
	if(board.empty())return 0;
	int minStep = -1;
	for(auto& p : hand)
	{
	char colorToApply = p.first;
	int j = 0;
	while(j < board.size())
	{
	int start = j;
	while(isdigit(board[j]))++j;
	char currColor = board[j];
	int secLen = stoi(board.substr(start, j - start));
	if(currColor == colorToApply && ((secLen < 3 && hand[colorToApply] >= 3 - secLen) || secLen >= 3))
	{
	//if we have ball to pad or it is already a section we can remove
	//we can remove a section and continue recursion
	//it is impossible for us to remove all balls of a color in a single round
	//for example : board "WWGWGW" hand "GWBWR"
	//we apply two W to remove middle W and we have "WWGGW",
	//Then apply G and we can remove all chars
	int steps = 0;
	if(secLen < 3)
	steps += 3 - secLen;
	string newBoard = board.substr(0, start);
	hand[colorToApply] -= steps;
	merge(newBoard, board.substr(j + 1));
	int nextSteps = applyHand(newBoard, hand);
	hand[colorToApply] += steps;
	if(nextSteps != -1)
	minStep = minStep == -1? steps + nextSteps: min(steps + nextSteps, minStep);
	}
	++j;
	}
	}
	return minStep;
	}
	};

view raw Zuma Game.cpp hosted with ❤ by GitHub

P.S. 第一次采取的做法是每一轮消去一个颜色的球，这样我们最多5轮就可以完事。但是这种做法是错误的，因为有无法一轮就消去一个颜色的情况，比如board "WWGWGW"和 hand "GWBWR"我们只能先消去中间的W之后，消去G之后再消去两端的W，我们是没有办法在一轮里消去所有的W的。