第一反应是尝试用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第二个。所以我们只需要统计手上每个颜色的球有多少个。
另外值得注意的几点：
- 每一个消去区间之后，可能board会出现需要merge的情况，比如"WRRWW"，手上的球为"R"，状态压缩之后的board为1W2R2W，apply "R"消去中间的R之后，board会变为1W2W，这时候我们需要将其merge为3W
- 不要提前消去大于3的区间，比如"WRRWWW"和"R"，最左边的W需要消去R之后和右边的三个merge在一起之后变为4W消去。我们只在apply ball的时候消去区间。
- 那么在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的，因为很多可能性都被我们剪枝剪掉了。代码如下：
P.S. 第一次采取的做法是每一轮消去一个颜色的球，这样我们最多5轮就可以完事。但是这种做法是错误的，因为有无法一轮就消去一个颜色的情况，比如board "WWGWGW"和 hand "GWBWR"我们只能先消去中间的W之后，消去G之后再消去两端的W，我们是没有办法在一轮里消去所有的W的。
No comments:
Post a Comment