动态编程:找到最大的三角形

Question

我需要使用动态编程在零和一个矩阵中找到最大的三角形.所以如果这是我的矩阵:

 1 0 0 1 1
 0 1 1 1 1
 0 1 1 1 0
 1 1 1 1 1
 1 1 0 0 1

然后在[2,2]和[4,4]处有两个最大的三角形,右角.我只需要寻找正确的等腰三角形(其角度为90°,45°,45°),我还需要只查看一个方向,因为所有其他方向都是对称的.所以基本上我需要一个函数,它接受矩阵并返回一个三角形,三角形是一个对象.我不需要完整的代码伪代码也很好.

首先我想到在这里使用方形算法:动态编程 - 最大的方块,当你找到最大的方块时,那么最大的三角形必须在那里.但我可以很容易地找到反效果的例子.在那之后我试着查看上面的单元格并用动态编程来计算它,但是我不知道下一步该怎么做...所以我的计数看起来像这样用上面的矩阵:

1 0 0 1 1
0 1 1 2 2
0 2 2 3 0
1 3 3 4 1
2 4 0 0 2

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

更新:

我认为我现在非常接近,当你遍历矩阵n*m并且使count [i] [j] = 1+ min(count [i-1] [j],count [i] [j-1] ),所以看左边和上面的细胞.我们得到这个:

1 0 0 1 1
0 1 1 2 2
0 1 2 3 0
1 2 3 4 1
1 2 0 0 1

这看起来对我很好,你可以看到[4,4]解决方案右角的位置.谁能想到任何反例？我只需要返回一个解决方案,所以返回此解决方案很好.

更新2: 我找到了一个反例,让位置[4,4]为0,然后得到以下矩阵:

 1 0 0 1 1
 0 1 1 1 1
 0 1 1 1 0
 1 1 1 0 1
 1 1 0 0 1

在遍历矩阵后,Count将如下所示:

1 0 0 1 1
0 1 1 2 2
0 1 2 3 0
1 2 3 0 1
1 2 0 0 1

现在它将返回右角[3,4](第三行第四列)的三角形,这是不正确的应该找到[2,2].所以我想也许只是从左上角(我们到目前为止所做的)和右下角并从中获取最大值.因此右下角的计数将如下所示(查看下方和右侧的单元格):

1 0 0 2 1
0 4 3 2 1
0 3 2 1 0
2 2 1 1 1
1 1 0 0 1

现在我们确实找到了[2,2]的解决方案.所以我认为使用这些方法会给我解决方案,任何人都可以想到更好的解决方案或这个方案的反例吗？

更新3: kraskevich让我意识到我们必须使用这种算法四次.从左上角,右上角,左下角,右下角然后只取最大值,因为那时你已经采取了所有的可能性.谁有更好的方法来做到这一点？这个算法是否正确？(因此,只有相同算法的四倍,矩阵中只有另一个起点)

另外对于那些不太了解我在做什么的人(我可能会快一点)再看看这个:动态编程 - 最大的方块这种方法非常相似,并且很好地解释了那里有什么完成.

Answer 1

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

宣称：

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

证明：

让我们使用归纳法。

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

归纳步骤：

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

1. f(i - 1, j) >= f(i, j) - 1之所以f(i, j - 1) >= f(i, j) - 1如此，是因为带有 s 的三角形的任何子三角形1都是带有 s 的三角形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成立。

2. 我们假设min(f(i - 1, j), f(i, j - 1)) = k. k然后单元格中有一个大小的三角形，单元格中有(i - 1, j)另一个大小的三角形。这两个三角形与细胞一起形成一个大小为 的三角形。因此，。k(i, j - 1)(i, j)k + 1f(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)时间（一般情况下，如果不查看矩阵的所有元素，我们就无法找到答案）。