動態規劃中的遞推公式

Question

其中l_1 = 1，l_2 = 4，l_3 = 5是不同長度的塊，我需要用公式構造一個長度爲l = 8的大塊。

有人可以解釋我以下公式：

的公式是在乳膠，與排列L = [1 + 1]

很抱歉的格式，但我`噸上傳圖片。

Answer 1

這個問題似乎是要找出做出更大塊所需的塊的最小數量是多少。此外，似乎沒有限制可用的單個塊的數量。

假設你有n個不同長度的塊。 l1, l2 .. ln。您可以用來製作一個長度爲k的大塊的最小塊數是多少？

的遞推公式背後的想法是，你可以通過添加長度l1的一個街區，你可能已經使用的塊的最小數目由長度i-l1的假設大塊使長度i塊（因爲這是你的L數組所持有的數據，對於任何索引j，它都包含製作大小爲j的塊所需的最小塊數。假設i-l1塊是使用4個塊建立的。使用這4個塊和另外一個大小爲l1的塊，您使用5個塊創建了一個大小爲i的塊。

但是現在說一個大小爲i-l2的塊只能使用3個塊。然後，您可以輕鬆地將另一個大小爲l2的區塊添加到此大小爲i-l2的區塊，並使用4個區塊創建一個大小爲i的區塊！

這就是對所有可能的塊長度進行迭代並選擇最小值（在乳膠圖像的第三行中提到）背後的想法。

希望有所幫助。