動態編程和矩陣的使用

Question

我總是對動態編程如何使用矩陣來解決問題感到困惑。我粗略地理解，矩陣用於存儲以前的子問題的結果，以便它可以用於稍後計算更大的問題。

但是，如何確定矩陣的維數，以及我們如何知道矩陣的每行/列應該表示什麼值？即，是否有像構造矩陣的通用程序那樣？

例如，如果我們有興趣使用值爲c1，c2，... cn的硬幣對S的金額進行更改，矩陣的維數應該是多少，以及每個列/行應該是多少代表？

任何方向指導都會有所幫助。謝謝！

Answer 1

對於某些類型的DP問題粗糙步驟：

1. 查找遞歸解決方案

2. 如果遞歸調用的一些中間結果被一次又一次計算 - 記住他們和使用 - 建立一個表適當的尺寸 - 這是記憶

3. 該表通常可以從起始單元到最終（結果） - 逐個單元，逐行等填充...

對於變化的問題：

1. F（S）= F（S-C1）+ F（S-C2）+ ...

儘量詳細完整的遞歸解決方案，並確定所需要的表來存儲由DP解決方案中使用的陣列幾乎總是基於對問題的狀態空間的尺寸的中間結果

Answer 2

- 也就是，對於每個其參數的有效值

例如

fib[i+2] = fib[i+1] + fib[i] 

相同

def fib(i): 
    return fib(i-1)+fib(i-2] 

您可以在您的遞歸函數

def fib(i): 
    if(memo[i] == null) 
     memo[i] = fib(i-1)+fib(i-2) 
    return memo[i] 

如果您的遞歸函數帶有K個參數實現記憶化使這個更加明顯，你可能需要一個K維矩陣。

Answer 3

本章對此進行了很好的解釋：http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf 在第178頁，它提供了一些方法來確定允許您應用動態編程的子問題。