動態規劃簡介：重疊子問題和最優子結構

已發表: 2021-02-08

介紹

假設我們有一個問題要解決 25 的平方。如果我們是第一次面對這個問題，那麼我們可以手頭或使用計算器來解決它。但是如果我們之前已經看過這個問題或者之前已經解決了這個問題，那麼我們有可能通過記住它來快速回答它。

這使我們得出結論，如果我們能記住它，那麼我們下次可以跳過它。動態編程的工作原理類似，其想法是記住計算結果並在將來需要時使用它。

這種簡單的動態編程過程使其成為程序員征服高效代碼之戰的有力武器。

例如，讓我們假設我們有一個複雜的問題，並且我們總是想一個將問題劃分為子問題的解決方案。但是我們可能會陷入多次計算子問題的情況。在那裡，我們使用動態規劃來獲得最佳解決方案。

動態規劃有兩個概念：

重疊子問題
最優子結構

重疊子問題

理解重疊子問題概念的一個經典例子是打印斐波那契數列的程序。

斐波那契數列的邏輯由“fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)”給出。並且可以使用遞歸解決方案無縫執行此功能，基本情況為 fibonacci(0)=0 和 fibonacci(1)=1。

公共靜態 int 斐波那契（int n）{
如果(n== 0 || n== 1 )
返回n;
返回斐波那契(n -1 )+斐波那契(n -2 )；
}
公共靜態無效主要（字符串[]參數）{
System.out.print( “第四個斐波那契數是“ +fibonacci( 4 ));
}

假設我們需要打印第 4 個斐波那契數字，那麼遞歸樹如下

斐波那契(4)

/ \

斐波那契 (3) + 斐波那契 (2)

/ \ / \

斐波那契 (2) + 斐波那契 (1) 斐波那契 (1) + 斐波那契 (0)

/ \

斐波那契 (1) + 斐波那契 (0)

請注意，斐波那契 (4) 是斐波那契數列中的第 5 位，因為我們從斐波那契 (0) 開始。在上面的遞歸樹中，我們可以看到 fibonacci(2) 重複了兩次。我們在高度為 4 的遞歸樹中觀察到重複，現在想像我們有一個巨大的遞歸調用，隨後，將有一個高度很大的遞歸樹。並且會有很多這樣的重複計算，稱為重疊子問題。

我們有兩種方法來處理這個（i）製表，（ii）記憶

讓我們通過它們的實現來了解它們。

記憶

使用記憶法解決斐波那契問題可以如下圖所示

靜態 int[] 備忘錄；
公共靜態 int 斐波那契（int n）{
如果（備忘錄[n]！=-1）
返回備忘錄[n];
如果（n==0 || n==1）{
備忘錄[n]=n;
返回 n;
}
備忘錄[n] = 斐波那契(n-1)+斐波那契(n-2);
返回備忘錄[n];
}
公共靜態無效主要（字符串[]參數）{
備忘錄=新的int [5]；
for(int i=0;i<=4;i++)
備忘錄[i]=-1;
System.out.println("第4個斐波那契數是"+fibonacci(4));
}

在上面的代碼中，我們正在創建一個維護日誌文件或維護一個查找表並存儲計算結果的值。由於我們已經記住了所有計算值，如果需要，我們可以在將來使用它們，從而避免重複計算和重疊子問題。

所有邏輯都類似於遞歸解決方案，但我們所做的唯一區別是我們在將值返回給 main 方法之前將它們記錄在 memo 數組中。該算法的唯一限制是我們需要一個大小為 O(n) 的額外空間，但我們正在優化之前的遞歸解決方案。

製表

此方法與上述解決方案略有不同。記憶遵循相同的遞歸解決方案。但在製表中，我們遵循迭代解決方案。它也被稱為自下而上的方法。讓我們看一下自下而上方法的實現。

公共靜態 int 斐波那契（int n）{
整數表[]=新整數[n+ 1 ]；
for (int i= 0 ;i<=n;i++){
如果(i== 0 || i== 1 )
表[i]=i;
否則{
表[i]=表[i -1 ]+表[i -2 ]；
}
}
返回表[n]；
}
公共靜態無效主要（字符串[]參數）{
System.out.println( “第4個斐波那契數是“ +fibonacci( 4 ));
}

我們知道 fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)，在記憶中我們從 fibonacci(4) 函數調用開始，然後我們意識到我們還沒有計算出它的值，所以我們'已經計算了它的值，然後存儲它。

像 fibonacci(3)、fibonacci(2) 這樣的進一步遞歸調用將面臨類似的情況。現在這使得很多遞歸調用在遞歸堆棧中等待，但無論如何我們都在跳過重疊子問題的重複。

我們還有一種方法可以迭代地計算從 0 到第 n 個元素的斐波那契，然後返回第 n 個斐波那契元素。這就是我們在上面的代碼中實現的。此代碼也具有相同的空間要求 O(n)。

結帳：成為全棧開發人員的技能

最優子結構

在這個概念中，只有最優地解決了相應的子問題，我們才能獲得問題的最優解。

這個概念的一個經典例子是考慮圖中節點之間的遍歷。

讓我們假設我們從 Telangana 到德里有多個根源。如果我們有經過那格浦爾和瓜廖爾的最短路線。那麼從那格浦爾到德里德里的最短路線必須經過瓜廖爾。現在我們可以將問題分解為子問題，即 Telangana 到那格浦爾、那格浦爾到 Gwalior、Gwalior 到德里。

這個屬性的一個經典例子是兩個字符串中最長的公共子序列。子序列不同於子串。在子序列中，字符不必在原始字符串中出現。

所以這個想法是通過優化解決它的子問題來解決它。設 n 為最長公共子序列的長度。

如果 n=LCS(potato, tattoo)，則 n=LCS(potat,tatto)+1（如果最後一個字符相同），否則 n=maximum(LCS(potato,tatto), LCS(potat, tattoo)。

靜態int lcs（字符串s1，字符串s2，int m，int n）{
int dp[][] = 新的 int[m+ 1 ][n+ 1 ];
for (int i= 0 ; i<=m; i++){
對於(int j= 0 ; j<=n; j++){
如果(i == 0 || j == 0 )
dp[i][j] = 0 ;
否則if (s1.charAt(i -1 ) == s2.charAt(j -1 ))
dp[i][j] = dp[i -1 ][j -1 ]+ 1 ;
別的
dp[i][j] = Math.max(dp[i -1 ][j], dp[i][j -1 ]);
}
}
返回dp[m][n]；
}
公共靜態無效主要（字符串[]參數）{
System.out.println( “最長公共子序列的長度是“ +lcs( “potato” , “tattoo” , 6 , 6 ));
}

在上面的代碼中，我們使用製表方法實現了我們的邏輯，併計算了兩個字符串中存在的最長公共子序列的長度。

另請閱讀：印度的全棧開發人員薪水

從世界頂級大學在線學習軟件開發課程。 獲得行政 PG 課程、高級證書課程或碩士課程，以加快您的職業生涯。

結論

既然您已經意識到使用其中一種強大的技術來征服高效代碼的戰鬥，請嘗試為其他問題實施動態編程，並開始增強您使用動態編程編寫問題的能力。

總而言之，全棧開發人員課程是高技能的專家，他們可以處理與 Web 開發相關的所有事情。這些全棧開發人員技能是他們與前端和後端開發人員的區別。

什麼是動態規劃？

計算機程序包含大量重複代碼。這是低效的，可能會影響其性能。在這種情況下，使用動態規劃。動態規劃是一種通過將復雜問題分解為更簡單的子問題來解決複雜問題的方法，這些子問題中的每一個只解決一次，並使用表格存儲它們的解決方案，然後在以後出現類似的子問題時查找這些表格複雜問題的解決方案。動態規划算法用於解決運籌學、統計估計、模式識別、人工智能、機器學習、計算生物學等領域的各類優化問題。

什麼是動態規劃中的重疊子問題？

重疊子問題是當子問題具有在其他子問題中使用的解決方案時使用的概念。這種重疊導致同一個子任務被多次解決。問題是找到一種只解決子任務一次的方法，並使用該解決方案來獲得其他子問題的解決方案。動態規划算法使用記憶化解決了這個問題。記憶是一種技術，我們存儲子問題的解決方案，這樣我們就不必再次解決它們。

動態規劃中的最優子結構是什麼？

最優子結構意味著問題的最優解與同一問題定義內較小問題的最優解相關。最優子結構是解決問題或證明沒有解決方案所需的附加要求。通過最優子結構，我們可以證明許多問題 NP-hard。解決DP問題的一般方法是使用動態規劃矩陣來存儲子問題的最優解。動態規劃矩陣可用於解決任何非零最優子結構 DP 問題。