哎哟。这个算法是错误的；没有证据，因为它是错误的，因此不可能证明它是正确的。;) 我把它留在这里是因为我太执着于完全删除它，这很好地说明了为什么你应该正式证明算法而不是说“这看起来不错！这不可能失败！”
我暂时给出这个解决方案没有证据。我有一个证明草图，但我无法证明这个问题的最佳子结构。反正...
问题
给定一个数字的方阵，选择尽可能多的“非重叠”数字，以使所选数字的总和最大化。“不重叠”意味着没有两个数字可以来自同一行或同一列。
算法
- 让
A是一个数字的方阵n by n。
- 让表示第 th 行和第 th 列中
Aij的元素。Aij
- 让表示包含行to和列to的交集的
S( i1:i2, j1:j2 )方形子数组的非重叠数字的最佳总和。Ai1i2j1j2
然后表示非重叠数的最佳总和，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()缓存结果，以便S(A,i1,i2,j1,j2)每个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,2vs.这样的关系1,3会被打破，有利于让所有单独的数字尽可能大（这样才能2,2获胜。）我相信你可以定义max()打破关系以支持最大的数字可能，这会做你想要的，但我无法证明这一点。
一般注意事项：
动态规划是一种强大的技术，可以为任何具有两个属性的问题设计快速算法：
- 最优子结构：一个问题可以分解成更小的部分，每个部分都可以作为原始问题解决方案的一部分。
- 重叠子问题意味着需要解决的实际子问题很少，并且子问题的解决方案被多次重复使用。
如果问题具有最优子结构，并且问题分解为更小的问题（例如，大小问题n分解为大小子问题），n-1则可以通过动态规划来解决问题。
如果您可以将问题分成更小的块 - 比如说将大小问题n分成两半，每个大小n/2- 那就是分而治之，而不是动态编程。分而治之的解决方案通常非常快——例如，二分搜索会O(log n)及时在排序数组中找到一个元素。