计算给定 n 的每行和每列中正好有 n/2 个零和 n/2 个 1 的矩阵数量
对于一个空白的 n * n 矩阵，甚至 n，我们想要为这个矩阵分配 0 和 1，所以 对于给定的 n，每行和每列恰好包含 n/2 个 0 和 n/2 个 1。
有没有动态规划的方法可以解决这个问题？我将基本情况设置为 0（大小为 0 的矩阵），然后将 2 个矩阵（n = 2）设置为 0。但是我无法得到递归方程。 我在最近接受微软采访时被问到了这个问题。
For a blank n * n matrix, even n, we want to assign zeros and ones to this matrix so
that each row and each column contains exactly n/2 zeros and n/2 ones for a given n.
Can there be a Dynamic programming method to solve this? I have worked the base case as 0 for a matrix of size 0, then 2 matrices for n = 2. But am not able to get the recursive equation.
I was asked this in a recent interview with Microsoft.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果您准备接受不切实际的大状态空间，那么您可以使用动态编程做任何事情。对于您的情况，假设我们从左到右按列工作。在步骤 k 处，我们将计算用包含 n/2 个 0 和 n/2 个 1 的列填充矩阵前 k 列的不同方式的数量，并且我们知道，对于每个不同的状态，不同的数量填充矩阵前 k-1 列的方法。
国家代表什么？我们需要它足够详细，以便在完成后我们知道每行包含 n/2 个 0 和 n/2 个 1。我想到的最好的情况是，状态告诉我们，对于每个可行的 i，到目前为止已收到 i 1 的行数。因此，在 4x4 矩阵的中间，我们的状态可能会告诉我们 2 行有 2 个 1，2 行有 0 个 1，或者，对于不同的状态，所有 4 行都收到一个 1。最后，我们只考虑与状态相关的计数告诉我们每行确实收到了 n/2 个 1。
对于我们的 4x4 示例，在 k = 1 时，只有一种可能的状态：2 行已收到单个 1，两行已收到单个 0。我们可以使用回溯搜索来计算出可能的后继状态 - 2 行有 2 1 行和 2 行有 0 个 1，1 行有 2 个 1，两个等分，1 行没有 1，或者 4 行全部等分。鉴于此，我们可以计算出属于每个状态的部分矩阵的数量。
这是一个动态编程解决方案，但是在计算出一个大矩阵的过程中，不同部分计数的数量本身就会很大，您可以看到编程并不简单。我想知道是否有更好的方法来做到这一点？
You can do anything with dynamic programming - if you are prepared to accept an impractically large state space. In your case, suppose we work in columns from left to right. At step k, we are about to count the number of different ways of filling up the first k columns of the matrix with columns containing n/2 0s and n/2 1s, and we know, for each different state, the number of different ways of filling up the first k-1 columns of the matrix.
What does a state represent? We need it to be detailed enough that, when we have finished, we know that each row contains n/2 0s and n/2 1s. The best I think of is that the state tells us, for each feasible i, the number of rows that have received i 1s so far. So, halfway through a 4x4 matrix, our state might tell us that 2 rows have 2 1s and 2 rows have 0 1s, or, for a different state, that all 4 rows have received a single 1. At the end, we consider only the counts associated with the state that tells us that every row really did receive exactly n/2 1s.
For our 4x4 example, at k = 1 there is only one possible state: 2 rows have received a single 1 and two rows have received a single 0. We could use a backtrack search to work out the possible successor states - 2 rows with 2 1s and 2 rows with 0 1s, 1 row with 2 1s, two with equal splits, and 1 row with no 1s, or 4 rows all with equal splits. Given that, we can work out the number of partial matrices belonging to each state.
This is a dynamic programming solution, but the number different partial counts halfway through working out a large matrix will itself be large, and you can see that the programming is non-trivial. I wonder if there is a better way to do this?
DP 看起来有点过分了。每个单元格将在零和一之间交替工作。像棋盘一样的东西。
DP looks like a over kill for this. Would alternating between zero and one for each cell work. Something like a chess board.
在这里找到了 DP 版本：
http://en.wikipedia.org/wiki/Dynamic_programming#A_type_of_balanced_0-1_matrix
Found the DP version of this here:
http://en.wikipedia.org/wiki/Dynamic_programming#A_type_of_balanced_0-1_matrix