假設我們有一堵n*3大小的墻，??有大小為1*3、2*3、 和3*3的磚塊，這些磚塊可以水平放置和垂直放置，那么排列磚塊填滿墻的方法總數是多少？這個問題的遞回關系是什么？
我認為它是T(n) = T(n-1) 2T(n-2) 7T(n-3)，因為T(n-2)我們1x3 1x3還是2x3如此2T(n-2)。對于三個，1x3 1x3 1x3，1x3 2x3或者2x3 1x3和水平相同，加上3x3所以我們有7dp(n-3)，這是正確的嗎？
謝謝！
uj5u.com熱心網友回復：
這幾乎是正確的，但它多計了幾個術語。例如，T(n-2) 的解 S 可以在它之后添加兩個垂直的 1-brick，成為 T(n) 的解。如果在 S 后添加一個 1-brick，則它是 T(n-1) 的解，因此排列 S 兩個 1-brick 將計入您的 T(n-2) 和 T(n-1) 項中。
相反，想想 T(n) 的解 S 如何在右邊結束。您可以證明(n-1) x 3S的初始段對 T(n-1) 有效當且僅當S 的最后一個塊是垂直 1-塊。
否則，(n-2) x 3S的起始段何時是S 的最長有效起始段？正是當 S 以垂直 2-block 結束時（如果它以兩個垂直 1-block 結束，則最長的有效初始段的長度為 n-1，我們已經計算過）。
最后一種情況是 n-3：找出最后一個3 x 3空間有多少種可能的配置，使得S 的最長有效初始段的長度為 n-3。作為提示：答案稱為“c”，它小于 7，正如您所展示的，它是3 x 3空間所有配置的計數。這些為您提供了遞回系數，T(n) = T(n-1) T(n-2) c*T(n-3)，n = 1、2 和 3 具有適當的基本情況。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/349065.html
上一篇：向量push_back()和使用[]的直接賦值給出不同的結果
下一篇：在未排序的陣列中找到第n個最小值