哎呀。
这个算法是错的；没有证明，因为它是错误的，所以无法证明它是正确的。;) 我把它留在这里，因为我太喜欢它了，而且它很好地演示了为什么你应该正式地证明算法，而不是说“这看起来对！没有可能失败！”
目前我还没有证明，但是我会提供这个解决方案。对于这个问题，我有一个证明草稿，但是我在证明这个问题的最优子结构时遇到了一些困难。无论如何...
问题
给定一个数字的正方形数组，选择尽可能多的“不重叠”的数字，使得所选数字的总和最大化。“不重叠”意味着任意两个数字不能来自同一行或同一列。
算法
- 令
A为一个由n x n个数字组成的正方形数组。
- 令
Aij表示A中第i行和第j列的元素。
- 令
S(i1:i2, j1:j2)表示包含行i1到i2和列j1到j2的交集的A的正方形子数组的最佳非重叠数字的总和。
那么最佳非重叠数字的总和表示为S(1:n, 1:n)，并且如下所示：
S( 1:n , 1:n ) = max { [ S( 2:n , 2:n ) + A11 ]
[ S( 2:n , 1:n-1 ) + A1n ]
[ S( 1:n-1 , 2:n ) + An1 ]
[ S( 1:n-1 , 1:n-1 ) + Ann ] }
(recursively)
Note that S( i:i, j:j ) is simply Aij.
也就是说，对于一个大小为n的正方形数组，可以通过分别计算大小为n-1的四个子数组的最优和，然后将子数组和被“遗漏”的元素的和最大化来确定最优和。
S for |# # # #|
|# # # #|
|# # # #|
|# # # #|
Is the best of the sums S for:
|# | | #| |# # # | | # # #|
| # # #| |# # # | |# # # | | # # #|
| # # #| |# # # | |# # # | | # # #|
| # # #| |# # # | | #| |# |
实现
上述递归算法建议使用递归解决方案：
def S(A,i1,i2,j1,j2):
if (i1 == i2) and (j1==j2):
return A[i1][j1]
else:
return max ( S( A, i1+1, i2, j1+1, j2) + A[i1][j1] ],
S( A, i1+1, i2, j1, j2-1) + A[i1][j2] ],
S( A, i1, i2-1, j1+1, j2) + A[i2][j1] ],
S( A, i1, i2-1, j1, j2-1) + A[i2][j2] ], )
请注意，这将使
O(4^n)次调用
S()！这比“暴力”解决方案的阶乘
O(n!)时间复杂度要好得多，但性能仍然很差。
重要的是要注意，许多调用具有相同的参数。例如，在解决3*3数组时，每个2*2数组都会被多次解决。
这表明有两种可能的解决方案可以加速：
- 使递归函数
S()缓存结果，这样它只需要为每个i1,i2,j1,j2计算一次S(A,i1,i2,j1,j2)。这意味着S()只需要计算O(n^3)个结果 - 所有其他请求都将从缓存中满足。(这被称为记忆化。)
- 不要从顶部开始，使用大的
n*n数组，并通过连续较小的子问题向下工作，而是从最小可能的子问题开始，从底部构建到n*n情况。这被称为动态规划。这也是O(n^3)，但它是一个更快的O(n^3)，因为你不必一直访问缓存。
动态规划解决方案的过程有点像：
- 找到所有1x1子数组的最优解（微不足道）。
- 找到所有2x2子数组的最优解。
- 找到所有3x3子数组的最优解。
- ...
- 找到所有n-1 * n-1子数组的最优解。
- 找到完整n*n子数组的最优解。
关于此解决方案的说明：
- 尚未证明。我正在努力。
- 您会注意到上面的算法只给出了
S()，即最优的和。它并没有告诉您哪些数字实际上构成了该和。您可以添加自己的回溯方法来找到解决方案的路径。
- 上述算法不能保证像
2,2与1,3这样的平局将被打破，以支持所有单个数字尽可能大（使2,2获胜）。我相信您可以定义max()以支持在最大可能数字的情况下打破平局，但我无法证明。
一般注释：
动态规划是一种强大的技术，可用于为展示以下两个特性的任何问题设计快速算法：
- 最优子结构：一个问题可以分解成稍微小一点的部分，每个部分都可以作为原问题的解的一部分来使用。
- 重叠子问题意味着要解决的实际子问题很少，并且子问题的解被多次重复使用。
如果问题具有最优子结构，并且问题分解成稍微较小的问题-比如大小为n的问题分解成大小为n-1的子问题-那么问题可以通过动态规划来解决。
如果您可以将问题拆分为明显更小的块-例如将大小为n的问题分成大小为n/2的两半，那么这就是分治法，而不是动态规划。分治法的解决方案通常非常快-例如，二分查找可以在O(log n)时间内找到排序数组中的元素。
O(n^3)的时间内运行。我必须将其写出并正式证明它的正确性。它应该比朴素递归解决方案具有显着更好的性能...只要我能证明它是有效的。 ;) - Li-aung Yip