动态规划：寻找最大三角形

Question

我需要使用动态规划在零和一的矩阵中找到最大的三角形。所以如果这是我的矩阵：

然后有两个最大的三角形，其右角在[2,2]和[4,4]。我只需要寻找直角等腰三角形（具有 90°、45°、45° 的角度），而且我也只需要查看一个方向，因为所有其他方向都是对称的。所以基本上我需要一个函数，它接受矩阵和 returns 一个三角形，三角形是一个对象。我不需要完整的代码伪代码也可以。

首先我想到这里只用正方形算法：Dynamic programming - Largest square block，当你找到最大的正方形时，那么最大的三角形肯定在那里。但我可以很容易地找到这不起作用的反例。之后我试着查看上面的单元格并使用动态编程对其进行计数，但我不确定下一步该怎么做......所以我的计数看起来像上面的矩阵：

我认为必须以某种方式使用它。

更新:

我想我现在已经很接近了，当你遍历矩阵 n*m 并使 count[i][j] = 1+ min(count[i-1][j], count[i] [j-1]), 所以看看左边和上面的单元格。我们得到这个：

这对我来说看起来很不错，你可以看到 [4,4] 解决方案的右上角在哪里。谁能想到任何反例？我只需要return一个解决方案，所以return这个解决方案很好。

更新 2： 我找到了一个反例，设位置[4,4]为0，我们得到如下矩阵：

遍历矩阵后计数将如下所示：

现在它将 return 右角为 [3,4] 的三角形（第三行第四列），这是不正确的，它应该找到 [2,2]。所以我想也许只是从左上角（我们到目前为止所做的）和右下角开始，然后从中取最大值。因此，右下角的计数将如下所示（查看下方和右侧的单元格）：

现在我们确实找到了[2,2]的解。所以我认为使用这些方法会给我解决方案，有人能想到更好的解决方案或反例吗？

更新 3： kraskevich 让我意识到我们必须使用这个算法四次。从左上角，右上角，左下角，右下角，然后取最大值，因为这样你就已经取了所有的可能性。任何人都有更好的方法来做到这一点？那么这个算法正确吗？（所以只是四次相同的算法，只是矩阵中的另一个起点）

对于那些不太了解我在做什么的人（我可能会说得有点快）再看看这个：Dynamic programming - Largest square block方法非常相似并且解释得很好那里已经完成了。

Answer 1

免责声明:

I did not merely restate what the OP is doing, in fact, the way we are updating the count is different.

我同意 @IVlad 我应该详细说明 为什么 我的解决方案中所述的算法有效，所以我编辑了我的答案以包括关键思想（我写的方法的观察部分）。

在我 post 编辑我的解决方案时，我完全不知道 OP 的方法（参见 revision history for evidence, the third revision was made by me），所以实际上我什至没有尝试重述 OP 正在做什么.我只是希望给出形式化描述问题的方法。

最初我一直试图避免 post 正确性的形式数学证明（因为 Whosebug 主要用于编码），我相信从我编写解决方案的方式来看，正确性应该是显而易见的可以直接从归纳推导出来。尽管如此，我还是应 OP 的要求在我的最新更新中包含了完整性证明。

=========================================== ===========================

解决方案

您可以使用与您引用的 post 中类似的方法。为了简单起见，我们只考虑在我们的讨论中找到左上角的直角三角形。将我们的方法推广到其他情况应该很简单。

我们定义了一个与输入矩阵大小相同的矩阵D，并将其所有条目初始化为0。我们想用 D[i][j] 来表示在 (i, j).

处转角的最大三角形（左上角为直角）的大小

我们的方法基于以下观察：

For a triangle of size n at (i, j), it is necessary that we have triangles of size (at least) n - 1 at both (i + 1, j) and (i, j + 1).

我们可以利用这个事实来计算 D 使用自下而上的方法。我们将通过许多遍迭代计算 D，在第 n 遍之后，我们将找到所有大小为 n 的三角形。我们将根据以下规则更新D：

在第一遍中，如果输入矩阵在(i, j)处有1，我们设置D[i][j] = 1。
在第 n 遍中，对于 D 中每个值为 n - 1 的条目（假设此条目位于 (i, j)，我们检查 D[i + 1][j] 和 D[i][j+1] 是否都等于 n - 1，如果是，我们设置 D[i][j] = n.
当我们遇到 D 的条目没有更新的传递时，我们终止我们的算法。

备注：第n遍实际上找到了大小为n的三角形的所有位置，我们将使用此信息更新下一步，这是 动态规划 中的关键思想 - 我们已经找到了较小子问题的解决方案，我们将用它来帮助解决更大的问题。

然后可以通过考虑 D 的最大条目找到最大三角形的大小（及其位置）。

正确性证明

这是通过数学归纳法得出的。

基本情况：如果在(i, j)处有一个大小为1的三角形，那么我们必须有D[i,j] = 1步（ 1) 我们的算法。

归纳步骤：假设我们已经找到所有大小为n - 1的三角形。对于大小为 n 的任何三角形，根据观察得出其右侧（即在 (i + 1, j) 处转角）和底部（即在 (i, j + 1) 处转角）的三角形的大小必须为 n - 1。根据我们的归纳假设，我们已经找到了这些三角形，因此通过我们算法的步骤 (2)，我们将得到 D[i, j] = n.

Answer 2

是的，你的想法几乎是正确的。让我们正式化吧。

索赔：

f(i, j) 是右下角在 (i, j) 位置的最大三角形的大小，计算正确。

证明：

让我们使用归纳法。

基本情况：对于第一行和/或第一列中的所有单元格，三角形的大小为一或零（取决于该单元格中的值）。

归纳步骤：

让我们假设 f(i - 1, j) 和 f(i, j - 1) 已被正确计算。

f(i - 1, j) >= f(i, j) - 1和f(i, j - 1) >= f(i, j) - 1。之所以如此，是因为1的三角形的任何子三角形都是1的三角形秒。它意味着 f(i, j) <= f(i - 1, j) + 1 和 f(i, j) <= f(i, j - 1) + 1，或者换句话说，f(i, j) <= min(f(i - 1, j) + 1, f(i, j - 1) + 1) = min(f(i - 1, j), f(i, j - 1)) + 1。因此，f(i, j) <= min(f(i - 1, j), f(i, j - 1)) + 1成立。
让我们假设 min(f(i - 1, j), f(i, j - 1)) = k。然后在 (i - 1, j) 单元格中有一个大小为 k 的三角形，在 (i, j - 1) 单元格中有另一个大小为 k 的三角形。这两个三角形与 (i, j) 单元格一起构成了一个大小为 k + 1 的三角形。因此，f(i, j) >= min(f(i - 1, j), f(i, j - 1)) + 1。

我刚刚展示了 f(i, j) >= min(f(i - 1, j), f(i, j - 1)) + 1 和 f(i, j) <= min(f(i - 1, j), f(i, j - 1)) + 1。这意味着 f(i, j) = min(f(i - 1, j), f(i, j - 1)) + 1。因此 f(i, j) 也被正确计算。

请注意，我们只考虑了直角位于右下角的三角形。为了考虑到所有可能的三角形，我们可以简单地运行这个算法来计算给定矩阵的所有 4 种可能的旋转。

让我们证明运行在 4 个方向上使用此算法是足够的：

矩阵中任意直角等腰三角形的直角只有四种可能的位置：左下角、右下角、左上角和右上角。运行这个算法在一个固定的方向上找到这个方向的最大三角形（我上面已经证明了）。因此，运行在所有可能的方向上使用该算法足以找到矩阵中的最大三角形。

这个算法在时间复杂度方面是最优的，因为它有 O(n * m) 的时间复杂度，仅仅读取输入已经需要 O(n * m) 的时间（我们不能在没有看到所有元素的情况下找到答案一般情况下的矩阵）。

Answer 3

这个解决方案非常聪明和优雅。我喜欢它！

但是，您可以稍微优化一下，因为以下断言并不完全正确：

For a triangle of size n at (i, j), it is necessary that we have triangles of size (at least) n - 1 at both (i + 1, j) and (i, j + 1).

这不是必要的条件。这是另一个（限制较少的）：

For a triangle of size n at (i,j) it is egnough that we have a triangle of size (at least) n - 1 in (i-1,j) and a segment of size (at least) n - 1 at the left of (i,j).

这个结果在矩阵中读取较少，因为使用累加器很容易找到段的大小。这导致读数减少约 33%。

这是该算法的可视化示例： http://jsfiddle.net/swvk32e8/1/

function solve() {
    var row, col;
    var i = 0;
    var n;
    var here,above;
    for (row = 1 ; row < SIZE ; row++) {
        n = grid[0 + SIZE * row];
        for (col = 1 ; col < SIZE ; col++) {
            here = grid[col + SIZE * row];
            if (here > 0) {
                if (n > 0) {
                    above = grid[col + SIZE * (row - 1)];
                    grid[col + SIZE * row] = 1 + Math.min(n, above);
                }
                n++;
            } else {
                n = 0;
            }
        }
    }
}

动态规划：寻找最大三角形

Dynamic programming: finding largest triangle

algorithm

dynamic-programming

pseudocode