对于一个空的n * n矩阵，其中n为偶数，我们想要将0和1分配给这个矩阵，使得每行和每列恰好包含n/2个0和n/2个1。
是否可以使用动态规划方法来解决这个问题？我已经处理了大小为0的矩阵的基本情况为0，然后对于n = 2，处理了两个矩阵。但是我无法得到递归方程。我最近在微软公司的面试中被问到了这个问题。
给定 n，计算每行和每列恰好有 n/2 个零和 n/2 个一的矩阵数量。
3
- Deepti Jain
3
这里有一个非常清晰的分析：http://www.netcomuk.co.uk/~jenolive/roymagic.html - user684934
我正在寻找一个递归方程。我认为我们必须为这个问题使用递归。 - Deepti Jain
我认为不存在递归方程，因为随着规模的增大，可能性不仅仅是组合更小规模的矩阵。例如，对于n=4，矩阵[1100,0110,0011,1001]根本没有大小为n=2的好子矩阵。 - Ante
3个回答
1
动态规划可以做任何事情 - 只要你愿意接受一个不切实际的大状态空间。在您的情况下，假设我们从左到右按列工作。在第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行都平均分配。鉴于此，我们可以计算出每个状态所属的部分矩阵数量。
这是一种动态规划解决方案，但在计算大型矩阵的中途，不同的部分计数数量本身就会很大，而且你可以看到编程并不容易。我想知道是否有更好的方法来解决这个问题？
- mcdowella
2
发现了这个链接：
http://en.wikipedia.org/wiki/Dynamic_programming#A_type_of_balanced_0-1_matrix - Deepti Jain
好吧，我猜你的面试官是在考虑这个，而不是我们错过了一些组合数学上的聪明想法。就我所看到的，那种方法更为直接且易于解释，但状态空间更大。 - mcdowella
0
对于这个问题，DP似乎有些过度了。在每个单元格之间交替使用零和一是否可行？就像棋盘一样。
- Dimitry
1
不行。你所指的可能会导致一种暴力方法来计算所有这样的矩阵，但必须有一种递归或更好的算法来计算这样的矩阵。暴力方法太昂贵了。 - Deepti Jain
0
- Deepti Jain
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接