algorithm - 在理解 "balanced 0-1 matrix"的动态编程方法方面需要帮助吗？

Question

问题:我正在努力理解/可视化“动态规划 - 维基百科文章中的一种平衡 0-1 矩阵”的动态规划方法。

维基百科链接:https://en.wikipedia.org/wiki/Dynamic_programming#A_type_of_balanced_0.E2.80.931_matrix

在处理多维数组时，我不明白内存是如何工作的。例如，当尝试用 DP 求解斐波那契数列时，使用数组存储先前状态的结果很容易，因为数组的索引值存储该状态的解。

谁能用更简单的方式解释“0-1 平衡矩阵”的 DP 方法？

Answer 1

维基百科提供了糟糕的解释和不理想的算法。但让我们以它为起点。

首先让我们来看看回溯算法。与其“按某种顺序”放置矩阵的单元格，不如将所有内容都放在第一行，然后是第二行，然后是第三行，依此类推。显然这会奏效。

现在让我们稍微修改一下回溯算法。我们将逐行进行，而不是逐个进行。所以我们列出了 n choose n/2 可能的行，其中一半是 0 一半是 1。然后有一个递归函数，看起来像这样:

def count_0_1_matrices(n, filled_rows=None):
    if filled_rows is None:
        filled_rows = []
    if some_column_exceeds_threshold(n, filled_rows):
        # Cannot have more than n/2 0s or 1s in any column
        return 0
    else:
        answer = 0
        for row in possible_rows(n):
            answer = answer + count_0_1_matrices(n, filled_rows + [row])
        return answer

这是一个类似于我们之前的回溯算法。我们只是一次做整行，而不是单元格。

但是请注意，我们传递的信息比我们需要的多。无需传递准确的行排列。我们只需要知道每个剩余列中需要多少个 1。所以我们可以让算法看起来更像这样:

def count_0_1_matrices(n, still_needed=None):
    if still_needed is None:
        still_needed = [int(n/2) for _ in range(n)]

    # Did we overrun any column?
    for i in still_needed:
        if i < 0:
            return 0

    # Did we reach the end of our matrix?
    if 0 == sum(still_needed):
        return 1

    # Calculate the answer by recursion.
    answer = 0
    for row in possible_rows(n):
        next_still_needed = [still_needed[i] - row[i] for i in range(n)]
        answer = answer + count_0_1_matrices(n, next_still_needed)

    return answer

这个版本几乎就是维基百科版本中的递归函数。主要区别在于我们的基本情况是，在每一行完成后，我们不需要任何东西，而维基百科会让我们编写基本情况的代码，以便在每一行完成后检查最后一行。

要从这个到一个自上而下的 DP，你只需要记住这个函数。在 Python 中，您可以通过定义然后添加 @memoize 装饰器来实现。像这样:

from functools import wraps

def memoize(func):
    cache = {}
    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

但还记得我批评维基百科算法吗？让我们开始改进吧!第一个大的改进是这个。您是否注意到 still_needed 的元素顺序并不重要，重要的是它们的值？因此，仅对元素进行排序将阻止您为每个排列分别进行计算。 (可以有很多排列!)

@memoize
def count_0_1_matrices(n, still_needed=None):
    if still_needed is None:
        still_needed = [int(n/2) for _ in range(n)]

    # Did we overrun any column?
    for i in still_needed:
        if i < 0:
            return 0

    # Did we reach the end of our matrix?
    if 0 == sum(still_needed):
        return 1

    # Calculate the answer by recursion.
    answer = 0
    for row in possible_rows(n):
        next_still_needed = [still_needed[i] - row[i] for i in range(n)]
        answer = answer + count_0_1_matrices(n, sorted(next_still_needed))

    return answer

那个无伤大雅的sorted 看起来并不重要，但它节省了很多工作!现在我们知道 still_needed 总是排序的，我们可以简化检查是否完成以及是否有任何负面结果的检查。另外，我们可以添加一个简单的检查来过滤掉列中有太多 0 的情况。

@memoize
def count_0_1_matrices(n, still_needed=None):
    if still_needed is None:
        still_needed = [int(n/2) for _ in range(n)]

    # Did we overrun any column?
    if still_needed[-1] < 0:
        return 0

    total = sum(still_needed)
    if 0 == total:
        # We reached the end of our matrix.
        return 1
    elif total*2/n < still_needed[0]:
        # We have total*2/n rows left, but won't get enough 1s for a
        # column.
        return 0

    # Calculate the answer by recursion.
    answer = 0
    for row in possible_rows(n):
        next_still_needed = [still_needed[i] - row[i] for i in range(n)]
        answer = answer + count_0_1_matrices(n, sorted(next_still_needed))

    return answer

并且，假设您实现了 possible_rows，这应该既有效又比维基百科提供的更有效。

=====

这是一个完整的工作实现。在我的机器上，它在 4 秒内计算出第 6 项。

#! /usr/bin/env python

from sys import argv
from functools import wraps

def memoize(func):
    cache = {}
    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

@memoize
def count_0_1_matrices(n, still_needed=None):
    if 0 == n:
        return 1

    if still_needed is None:
        still_needed = [int(n/2) for _ in range(n)]

    # Did we overrun any column?
    if still_needed[0] < 0:
        return 0

    total = sum(still_needed)
    if 0 == total:
        # We reached the end of our matrix.
        return 1
    elif total*2/n < still_needed[-1]:
        # We have total*2/n rows left, but won't get enough 1s for a
        # column.
        return 0
    # Calculate the answer by recursion.
    answer = 0
    for row in possible_rows(n):
        next_still_needed = [still_needed[i] - row[i] for i in range(n)]
        answer = answer + count_0_1_matrices(n, tuple(sorted(next_still_needed)))

    return answer

@memoize
def possible_rows(n):
    return [row for row in _possible_rows(n, n/2)]


def _possible_rows(n, k):
    if 0 == n:
        yield tuple()
    else:
        if k < n:
            for row in _possible_rows(n-1, k):
                yield tuple(row + (0,))
        if 0 < k:
            for row in _possible_rows(n-1, k-1):
                yield tuple(row + (1,))

n = 2
if 1 < len(argv):
    n = int(argv[1])

print(count_0_1_matrices(2*n)))