algorithm - 如何应用动态规划来寻找在田地中 build 塔的最低成本

Question

给定一个 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  

Input 中的 4 行是树的坐标，连根拔起的成本是第三个整数。

与塔的边缘重合的树被认为是放置在塔内，也必须连根拔起。

我在为这个问题制定动态规划关系时遇到问题

谢谢

Answer 1

听起来您的问题可以归结为:找到 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 。