什麼是動態規劃的新手解釋？

Question

我想學習動態規劃（DP）的基礎知識，並通過一些網上資源，我能得到，比如去......

1. What is dynamic programming?
2. Good examples, articles, books for understanding dynamic programming
3. Tutorial for Dynamic Programming
4. Dynamic Programming – From Novice to Advanced - （我不能正確理解它（即如何使用DP來解決問題））

並且直到n嗷嗷我得到理解

一個動態的問題是幾乎相同的是的 遞歸只需差異（這給它，它是知道 爲電源）

即存儲價值或解決方案，並再次使用它來尋找下一個解決方案

例如：

據codechef

問題的說明：最小的步驟的一個

問題陳述：在一個正整數，則可以執行以下3個步驟的任何一個。

1. 從它減去1。 （N = N - 1）
2. 如果其被2整除，除以2（如果n％2 == 0，則n = N/2）
3. 如果其被3整除，除以3（如果n％3 == 0，則n = N/3）

現在的問題是，給定一個正整數n，找到的步驟的最小數目取n設置爲1

例如：

1. 對於n = 1，輸出：0
2. 對於n = 4，輸出：2（4/2 = 2/2 = 1）

3. 對於n = 7，輸出：3（7 -1 = 6/3 = 2/2 = 1）

   int memo [n + 1]; //我們將初始化元素爲-1（-1表示，不解決它尚未）

自上而下的方法對上述問題

int getMinSteps (int n) { 
    if (n == 1) return 0; 
    if(memo[n] != -1) return memo[n]; 
    int r = 1 + getMinSteps(n - 1); 
    if(n%2 == 0) r = min(r , 1 + getMinSteps(n/2)); 
    if(n%3 == 0) r = min(r , 1 + getMinSteps(n/3)); 
    memo[n] = r ; // save the result. If you forget this step, then its same as plain recursion. 
    return r; 
} 

我在瞭解DP糾正，或者任何人都可以用更好更簡單的方式解釋它，這樣我就可以學習它，並且可以用動態編程解決問題。

Answer 1

維基百科的Fibonacci sequence示例給出了一個很好的例子。

動態規劃是一種優化技術，它將潛在的指數遞歸解轉化爲多項式時間解，假設問題滿足principle of optimality。基本上意味着你可以從最優的子問題構建最優的解決方案。 動態規劃易於處理的另一個重要問題是它們是overlapping。如果這些問題被分解爲重複的子問題，則可以重複使用相同的解決方案來解決這些子問題。 最佳子結構屬性和重疊子問題存在問題，動態規劃是一種解決問題的潛在有效方法。

在這個例子中，你可以看到斐波那契數的遞歸版本會像結構一樣在一棵樹中生長，這意味着指數爆炸。

function fib(n) 
     if n <=1 return n 
     return fib(n − 1) + fib(n − 2) 

所以對於fib(5)你：

fib(5) 
fib(4) + fib(3) 
(fib(3) + fib(2)) + (fib(2) + fib(1)) 

等都在喜歡時尚的一棵樹。

動態編程允許我們在多項式時間內使用最優子問題遞增地構建解決方案。這通常通過某種形式的記錄如表格來完成。 請注意，有重複的子問題的實例，即一次計算fib（2）就足夠了。

維基百科

此外，動態編程解決方案

function fib(n) 
    if n = 0 
     return 0 
    else 
     var previousFib := 0, currentFib := 1 
     repeat n − 1 times // loop is skipped if n = 1 
      var newFib := previousFib + currentFib 
      previousFib := currentFib 
      currentFib := newFib 
    return currentFib 

這裏的解決方案是從previousFib和currentFib這是最初設定建立。 newFib根據此循環中的前幾個步驟進行計算。 previousFib和currentFib代表我們記錄以前的子問題。

結果是一個多項式時間解決方案（在這種情況下爲O（n）），其遞歸公式在這種情況下是指數的（O（2^n））。