您将获得一个 N X M 矩形区域，其左下点位于原点。你必须在田野里 build 一座方形底座的塔。田里有树，连根拔起它们都会产生相关费用。所以你必须尽量减少被连根拔起的树木数量，以尽量减少 build 塔的成本。
输入示例:
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 子 block 。您可以使用积分变换有效地解决此问题(与输入的大小成比例)。当然，这并不一定能帮助您解决动态编程问题——我不确定这个解决方案是否等同于任何动态编程公式......
无论如何，对于每个索引对 (a,b)原始矩阵 M ，计算“积分变换”矩阵I[a,b] = sum[i<=a, j<=b](M[i,j]) 。这可以通过按顺序遍历矩阵来计算，引用从前一行/列计算的值。 (稍微思考一下，您也可以使用稀疏矩阵有效地做到这一点)
然后，您可以计算任意子 block (a1..a2, b1..b2) 的总和在恒定时间内 I[a2,b2] - I[a1-1,b2] - I[a2,b1-1] + I[a1-1,b1-1] 。迭代所有 KxK 子 block 以找到最小和所需的时间也与原始矩阵的大小成正比。
由于原始问题被表述为整数坐标列表(并且大概期望塔位置作为整数坐标对输出)，因此您可能确实需要将您的字段表示为稀疏矩阵以获得有效的解决方案-- 这涉及按字典顺序对树的坐标进行排序(例如，首先按 x 坐标，然后按 y 坐标)。请注意，此排序步骤可能需要 O(L log L)用于输入尺寸L ，主导以下步骤，只需要 O(L)输入的大小。
另请注意，由于指定“与塔边缘重合的树被连根拔起...”的问题，边缘长度为 K 的塔实际上对应于 (K+1)x(K+1)子 block 。
关于algorithm - 如何应用动态规划来寻找在现场 build 塔的最低成本，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16023432/