python - 如何找到覆盖屋顶孔洞所需的最少瓷砖数量

Question

我刚刚学习动态规划，我偶然发现了一个我不确定如何用 Python 表述的问题:

Given a binary array H of length 55, a 1 indicates a hole in the roof, 0 indicates no hole. The tails you can use have length 1, 13 or 55, and the cost to deploy each is 3, 13 and 50, respectively. For a given array of holes H return the minimum cost such that all the holes are covered.

据我所知，第一步是找到基本案例，然后通过归纳推理。 因此，这里有一些我可以轻松找到的基本案例:

• 一 block 13 号的瓷砖比 5 block 1 号的瓷砖更方便(成本:13 比 15 或更多)
• 一 block 55 号的瓷砖比 4 block 13 号的瓷砖更方便(成本:50 比 52 或更多)

最初我认为第一点意味着如果在 13 个连续的空间中有 5 个或更多的洞，我应该总是选择 13 block 瓷砖。但是我认为这取决于以下漏洞。

如果你在问题中加入 1-tiles，第二点就更成问题了。例如，考虑在 [0, 15, 29, 44] 位置有 4 个单孔，最好使用 4 个 1-tile(1 x 55-tile 成本为 50、4 x 13-tile = 52).

所以看起来我必须评估数组中所有可能的切片组合的孔的“间距”。

我如何将以上内容表述为(甚至是伪)代码？

Answer 1

假设成本 [i] - 覆盖屋顶前 i 个元素的最佳成本。 显然 cost[0] = 0(我们不需要任何钱来覆盖 0 个图 block )。

让我们将状态描述为(位置，成本)。

从状态 (i,cost[i]) 我们可以得到 4 种不同的潜在状态:

• (i + 1, cost[i] + 3)(当我们使用长度为 1 且成本为 3 的瓦片时)
• (i + 13, cost[i] + 13) (tile 长度 = 13, cost 也是 13)
• (i + 55, cost[i] + 50)(图 block 长度 = 55，成本为 50)
• (i + 1, cost[i])(我们忽略当前位置，这里不使用任何图 block )

一旦我们使用上述规则之一更改状态，我们应该考虑:

• 位置应 <= 总长度 (55)
• 如果我们以相同或更大的成本到达位置 i，我们不想继续(基本上动态规划在这里起作用，如果我们以相同或更差的结果到达子问题，我们不想继续)。
• 如果这个瓦片有洞，我们不能跳过瓦片(我们的第四个状态转换)。

一旦我们运行所有这些状态转换，答案将以成本[总长度 (55)] 为代价