如何找到覆蓋孔在屋頂

Question

我只是學習有關動態編程所需要的瓷磚的最小數目，我已經在這，我不知道如何在Python制定一個問題跌跌撞撞：

給定長度爲55的二進制數組H,1表示屋頂上有洞，0表示沒有洞。 您可以使用的尾巴長度爲1，13或55，每個部署的成本分別爲3,13和50。 對於給定的孔陣列H返回最小成本，使得所有的孔都被覆蓋。

從我所瞭解到的，第一步是找到基礎案例，並通過歸納推理。 因此，這裏有一些基本的情況下，我可以很容易地發現：

• 13號的瓷磚低於5瓦的大小1更方便（費用：13 VS 15人以上）
• 大小55瓦比4塊13號的磚更方便（成本：50 vs 52或更多）

最初我認爲第一點意味着如果在13個連續的空間中有5個或更多的洞，我應該總是選擇13塊。不過，我認爲這取決於以下漏洞。

如果你在問題中引入1-tiles，第二點就更成問題了。考慮一下，例如，在[0, 15, 29, 44]位置有4個單洞，最好使用4個1-tiles（1 x 55-tile費用50,4 x 13-tiles = 52）。

所以它看起來我必須評估「多少間隔」是陣列中切片的所有可能組合的孔。

我怎樣才能將上述內容編入（甚至是僞代碼）？

Answer 1

可以說成本[i] - 最好的成本來覆蓋屋頂的第一個元素。 顯然成本[0] = 0（我們不需要任何金錢來覆蓋0瓦片）。

讓我們描述我們的狀態（位置，成本）。

從狀態（I，成本[I]），我們可以得到4種不同的電勢狀態：

• 第（i + 1，成本[I] + 3）（當我們使用長度爲1的瓷磚和成本是3）
• （i + 13，成本[i] +13）（平鋪長度= 13，成本也是13）
• （i + 55，成本[i] +50） ，成本是50）
• 第（i + 1，成本[I]）（我們忽略當前位置和在這裏不使用任何瓦）

一旦我們改變使用上述規則的一個狀態，我們應該考慮：

• 位置應該< =總長度（55）
• 如果我們定位我具有相同或更大的成本我們不我們不想繼續下去（基本上動態編程在這裏起作用，如果我們遇到相同或更糟糕的結果，我們不想繼續）。
• 如果這個瓷磚有洞，我們不能跳過瓷磚（我們的第四個狀態轉換）。

一旦我們運行所有的這種狀態轉變回答將在成本[總長度（55）]