对于一个空白的 n * n 矩阵，即使是 n，我们想给这个矩阵分配 0 和 1，所以 对于给定的 n，每一行和每一列恰好包含 n/2 个零和 n/2 个一。
有没有动态规划的方法可以解决这个问题？对于大小为 0 的矩阵，我将基本情况设为 0，然后将 n = 2 设为 2 个矩阵。但是我无法得到递归方程。 我在最近接受 Microsoft 采访时被问到这个问题。
最佳答案
如果您准备好接受不切实际的大状态空间，您可以使用动态规划做任何事情。在您的情况下，假设我们从左到右按列工作。在第 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 行都有相等的分割。鉴于此，我们可以计算出属于每个状态的部分矩阵的数量。
这是一个动态规划的解决方案，但是在计算出一个大矩阵的过程中，不同部分计数的数量本身就很大，你可以看到规划是不平凡的。我想知道是否有更好的方法来做到这一点？
关于java - 计算给定 n 的每行和每列中正好有 n/2 个零和 n/2 个的矩阵数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7990017/