代碼日亞麻布佈局的出現

第 19 天：亞麻布佈局

GitHub 解決方案

今天的挑戰與通常的 2D 謎題和 Dijkstra 演算法相比有令人耳目一新的變化。以下是我的處理方法：

第 1 部分

目標很簡單：檢查是否可以使用可用的毛巾建立給定的毛巾佈置。

不應該做什麼：

最初，我嘗試使用 itertools.combinations 產生所有可能的毛巾組合。很快我們就發現這既不實用也不有效率。

什麼有效：

使用遞歸結合字典（備忘錄）來快取已經處理過的設計。這可以防止冗餘計算並使解決方案更有效率。

工作原理：

對於每個設計，請嘗試將開頭與其中一種毛巾圖案相匹配。
如果存在匹配，則刪除匹配的部分並對剩餘部分進行遞歸。
使用備忘錄快取我們已經檢查過的設計結果，避免重複工作。
具有記憶功能的遞歸方法使複雜性保持可控，即使對於較大的輸入也是如此，並使解決方案高效運作。

第二部
第二部分提高了賭注：計算使用可用圖案製作每條毛巾設計的方法數。

關鍵見解：
count_arrangements 函數擴展了第 1 部分中的遞歸邏輯，但現在計算建置設計的所有可能方法。

對於每條匹配的毛巾，遞歸設計的其餘部分。
使用另一個字典（memo_count）來快取先前解決的子問題的結果。

範例：
如果「brgr」可以透過兩種方式構造，我們只需從快取中傳回 2，而不是重新計算它。

最佳化：
感謝第 1 部分，我們已經知道哪些設計是可能的。我們只計算這些的安排。

for arrangement in arrangements:
    if arrangement in memo and memo[arrangement]:
        ways = count_arrangements(arrangement, towels, memo_count)
        total_arrangements += ways

透過總結所有有效的方法，我們得到了第二部分的最終答案，就這麼簡單。

就像我說的，我發現今天的挑戰很有趣，是一個很好的改變。我希望這篇文章對未來的挑戰/編碼有所幫助。

一如既往，請隨時在 Twitter 上關注我或聯繫我

以上是代碼日亞麻布佈局的出現的詳細內容。更多資訊請關注PHP中文網其他相關文章！