如果将硬币放在网格上，并且只能翻转整行或整列，我们如何翻转硬币以获得最少的尾数。
我尝试使用贪婪的解决方案，在该解决方案中，我翻转了尾数大于头数的行或列，并重复该过程，直到数字没有变化为止。但是我发现这种方法有时无法为我提供最佳解决方案。
HHT
THH
THT
例如，如果将硬币放置在上面，并且我以下面的方式翻转硬币，则获得的值为3，但实际上答案为2。
1. Flip the row 3
HHT
THH
HTH
2. Then there exists no row or column where the number of tails are greater than that of heads.
3. But if I flip the column 3, row 3, column 1, there exists a solution whose value is 2.
THH
HHT
HHH
因此，我认为上述算法不起作用。我应该使用哪种方法和算法？
最佳答案
首先让我们注意到，将同一行或列翻转两次或更多次是没有意义的(更好的解决方案总是将行/列翻转为零或一次)，并且翻转行或列的顺序无关紧要，所以我们可以将解决方案描述为长度为2N的位数组。每行一位，每列一位。如果我们将行/列翻转一次，则为on；如果我们将其翻转零次，则为off。
因此，我们需要搜索2 ^(2N)个可能的解，而首选具有更多零的解。
其次，让我们注意到，对于一种解决方案，硬币有四种可能的状态:
请注意，状态1和状态4会产生硬币的原始值
还要注意，状态2和3与硬币的原始值相反
首先将硬币的原始状态表示为二进制矩阵(B)。 2N位字段是2个二进制向量(R，C)，尾部总数是此f(B，R，C)的函数，而位数是函数g(
V_1，V_2)因此，您的目标是在最小化g的同时使f> =最小。
想想一下，如果我们首先修复我们的R配置(我们将翻转哪些行)，那么如何仅针对C(我们将翻转哪些列)解决问题？换句话说，考虑更简单的问题，即只允许翻转列，而不允许翻转行。您将如何解决？ (提示:DP)您现在可以将此策略扩展到整个问题吗？
关于algorithm - 多次翻转整行或整列后，获得硬币的最小尾数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17261425/