你得到一个N X M矩形场，左下角在原点。你必须在野外建造一座方形底座的塔。田地里有树，连根拔起它们的成本都很高。因此，您必须尽量减少连根拔起的树木数量，以最大限度地降低建造塔的成本。
示例输入：
N = 4
M = 3
Lenght of side of Tower = 1
Number of Trees in the field = 4
1 3 5
3 3 4
2 2 1
2 1 2
输入中的 4 行是树的坐标，其中第三个整数是根除成本。
与塔边缘重合的树被视为放置在塔内，也必须连根拔起。
我在为这个问题制定动态规划关系时遇到了问题
谢谢
听起来您的问题归结为：找到具有最小和的 MxN 矩阵的 KxK 子块。您可以通过使用积分变换有效地解决此问题（与输入的大小成正比）。当然，这不一定能帮助您解决动态编程问题——我不确定这个解决方案是否等同于任何动态编程公式......
无论如何，对于(a,b)原始矩阵的每个索引对M，计算一个“积分变换”矩阵I[a,b] = sum[i<=a, j<=b](M[i,j])。这可以通过按顺序遍历矩阵来计算，参考从前一行/列计算的值。（稍加思考，您也可以使用稀疏矩阵有效地做到这一点）
然后，您可以将(a1..a2, b1..b2)恒定时间内的任何子块的总和计算为I[a2,b2] - I[a1-1,b2] - I[a2,b1-1] + I[a1-1,b1-1]。遍历所有 KxK 子块以找到最小的总和将花费与原始矩阵大小成正比的时间。
由于原始问题被表述为积分坐标列表（并且可能期望塔位置作为积分坐标对输出），因此您可能确实需要将您的字段表示为稀疏矩阵以获得有效的解决方案 - 这涉及按字典顺序对树的坐标进行排序（例如，首先按x-coordinate，然后按y-coordinate）。请注意，此排序步骤可能需要O(L log L)size 的输入L，支配以下步骤，这些步骤仅需要O(L)输入的大小。
还要注意，由于指定“与塔边缘重合的树被连根拔起......”的问题，边长为 K 的塔实际上对应于一个(K+1)x(K+1)子块。