構建 DP 解決方案

Created: November-22, 2018

無論你使用動態程式設計（DP）解決了多少問題，它仍然會讓你感到驚訝。但作為生活中的其他一切，練習會讓你變得更好。記住這些，我們將看看構建 DP 問題解決方案的過程。有關此主題的其他示例將幫助你瞭解 DP 是什麼以及它是如何工作的。在此示例中，我們將嘗試瞭解如何從頭開始提供 DP 解決方案。

迭代 VS 遞迴：
有兩種構造 DP 解決方案的技術。他們是：

迭代（使用 for-cycles）
遞迴（使用遞迴）

例如，用於計算兩個字串 s1 和 s2 的最長公共子序列的長度的演算法如下所示： **** ****

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

這是一個迭代的解決方案。以這種方式編碼的原因有幾個：

迭代比遞迴更快。
確定時間和空間複雜性更容易。
原始碼簡短而乾淨

檢視原始碼，你可以輕鬆瞭解其工作原理和原因，但很難理解如何提出此解決方案。然而，上述兩種方法轉換為兩種不同的虛擬碼。一個使用迭代（Bottom-Up），另一個使用遞迴（Top-Down）方法。後者也稱為記憶技術。然而，這兩種解決方案或多或少是等價的，並且可以很容易地轉換成另一種解決方案。在本例中，我們將展示如何為問題提出遞迴解決方案。

示例問題：
假設你將 N （ 1,2,3，….，N ）葡萄酒放在架子上彼此相鄰。我的葡萄酒的價格是 p [i] 。葡萄酒的價格每年都在上漲。假設這是第 1 年，在第 y 年，第 i 個葡萄酒的價格將是：年份*葡萄酒的價格= y * p [i] 。你想要出售你所擁有的葡萄酒，但從今年開始，你每年必須出售一種葡萄酒。同樣，每年，你只能出售最左邊或最右邊的葡萄酒，而不能重新排列葡萄酒，這意味著它們必須保持與開始時相同的順序。

例如：假設你在貨架上有 4 種葡萄酒，價格是（從左到右）：

+---+---+---+---+
| `1` | 4 | 2 | 3 |
+---+---+---+---+

最佳解決方案是以 1 - > 4 - > 3 - > 2 的順序出售葡萄酒，這將為我們帶來以下總利潤： StackOverflow 文件

貪婪的方法：
經過一段時間的頭腦風暴，你可能會想出儘可能晚地出售昂貴的葡萄酒的解決方案。所以你的貪婪策略將是：

Every year, sell the cheaper of the two (leftmost and rightmost) available wines.

儘管該策略沒有提及當兩種葡萄酒的成本相同時該怎麼做，但這種策略有點合適。但不幸的是，事實並非如此。如果葡萄酒的價格是：

+---+---+---+---+---+
| `2` | 3 | 5 | 1 | 4 |
+---+---+---+---+---+

貪婪的策略會以 1 - > 2 - > 5 - > 4 - > 3 的順序出售它們，總利潤為： StackOverflow 文件

但是，如果我們以 1 - > 5 - > 4 - > 2 - > 3 的順序出售葡萄酒，我們可以做得更好，總利潤為： StackOverflow 文件

這個例子應該讓你相信這個問題並不像第一眼看上去那麼容易。但它可以使用動態程式設計來解決。

回溯：
為找到回溯解決方案的問題提出 memoization 解決方案非常方便。Backtrack 解決方案評估問題的所有有效答案並選擇最佳答案。對於大多數問題，更容易提出這樣的解決方案。在處理回溯解決方案時可以遵循三種策略：

它應該是一個使用遞迴計算答案的函式。
它應該返回帶有 return 語句的答案。
所有非區域性變數都應該用作只讀，即函式只能修改區域性變數及其引數。

對於我們的示例問題，我們將嘗試出售最左邊或最右邊的葡萄酒並遞迴計算答案並返回更好的答案。回溯解決方案看起來像：

// year represents the current year
// [begin, end] represents the interval of the unsold wines on the shelf
Procedure profitDetermination(year, begin, end):
if begin > end                  //there are no more wines left on the shelf
    Return 0
Return max(profitDetermination(year+1, begin+1, end) + year * p[begin], //selling the leftmost item
           profitDetermination(year+1, begin, end+1) + year * p[end])   //selling the rightmost item

如果我們使用 profitDetermination(1, 0, n-1) 呼叫該程式，其中 n 是葡萄酒的總數，它將返回答案。

這個解決方案只是嘗試銷售葡萄酒的所有可能的有效組合。如果一開始就有 n 種葡萄酒，它將檢查 StackOverflow 文件可能性。即使我們現在得到正確答案，演算法的時間複雜度也呈指數級增長。

正確編寫的回溯函式應始終代表一個明確問題的答案。在我們的例子中，程式 profitDetermination 代表了一個問題的答案： *當今年是年份並且未售出的葡萄酒的間隔跨越[開始]時，我們可以通過銷售儲存在陣列 p 中的價格獲得的最佳利潤是多少？，結束]，包容性？*你應該總是嘗試為你的回溯函式建立一個這樣的問題，看看你是否正確，並確切瞭解它的作用。

確定狀態：
狀態是 DP 解決方案中使用的引數數量。在這一步中，我們需要考慮傳遞給函式的哪些引數是多餘的，即我們可以從其他引數構造它們，或者根本不需要它們。如果有任何這樣的引數，我們不需要將它們傳遞給函式，我們將在函式內部計算它們。

在上面顯示的示例函式 profitDetermination 中，引數 year 是冗餘的。它相當於我們已售出的葡萄酒數量加一。可以使用從開始的葡萄酒總數減去我們未售出的葡萄酒數量加上一個來確定。如果我們將葡萄酒總數 n 儲存為全域性變數，我們可以將函式重寫為：

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
year := n - (end-begin+1) + 1        //as described above
Return max(profitDetermination(begin+1, end) + year * p[begin],
           profitDetermination(begin, end+1) + year * p[end])

我們還需要考慮可以從有效輸入獲得的引數的可能值範圍。在我們的示例中，begin 和 end 中的每個引數都可以包含從 0 到 n-1 的值。在有效的輸入中，我們也期望 begin <= end + 1。可以使用 O(n²) 不同的引數呼叫我們的函式。

記憶：
我們現在差不多完成了。為了將具有時間複雜度的回溯解決方案轉換為具有時間複雜度的 StackOverflow 文件 memoization 解決方案，我們將使用一個不需要太多努力的小技巧。

如上所述，只有 StackOverflow 文件不同的引數可以呼叫我們的函式。換句話說，我們實際上只能計算不同的東西。那麼時間複雜性來自何處以及它的計算內容！

答案是：指數時間複雜度來自重複遞迴，因此，它一次又一次地計算相同的值。如果你為 n = 20 個葡萄酒的任意陣列執行上面提到的程式碼，並計算為引數 begin = 10 和 end = 10 呼叫函式的次數，你將得到一個數字 92378 。多次計算相同的答案是浪費大量時間。我們可以做些什麼來改進它，一旦我們計算了它們就儲存了值，每次函式請求已經計算的值時，我們不需要再次執行整個遞迴。我們將有一個陣列 dp [N] [N] ，用 -1 （或我們的計算中不會出現的任何值）初始化它，其中 -1 表示尚未計算的值。陣列的大小由 begin 和 end 的最大可能值決定，因為我們將在陣列中儲存某些 begin 和 end 值的相應值。我們的程式如下：

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
if dp[begin][end] is not equal to -1                //Already calculated
    Return dp[begin][end]
year := n - (end-begin+1) + 1
dp[begin][end] := max(profitDetermination(year+1, begin+1, end) + year * p[begin],
           profitDetermination(year+1, begin, end+1) + year * p[end])
Return dp[begin][end]

這是我們所需的 DP 解決方案。使用我們非常簡單的技巧，解決方案執行 StackOverflow 文件時間，因為有不同的引數可以呼叫我們的函式，對於每個引數，函式只執行一次複雜。

總結：
如果你可以確定可以使用 DP 解決的問題，請使用以下步驟構建 DP 解決方案：

建立回溯功能以提供正確答案。
刪除多餘的引數。
估計並最小化函式引數的可能值的最大範圍。
嘗試優化一個函式呼叫的時間複雜度。
儲存值，以便你不必計算兩次。

在一個 DP 溶液的複雜性是： 可能值的範圍中的功能可與被稱為 * 時間每次呼叫的複雜性。