最近複習了下動規和貪心算法，借助 GPT 幫忙總結了下。
動態規劃和貪心算法的區別#
總的來說，如果問題滿足最優子結構和重疊子問題，那麼可以考慮使用動態規劃。如果問題滿足最優子結構，以及可以通過局部最優解達到全局最優解（貪心選擇性質），那麼可以考慮使用貪心算法。如果問題同時滿足上述所有特性，那麼可能既可以使用動態規劃，也可以使用貪心算法，具體選擇哪種取決於實際問題的需求和限制。
- 子問題重疊
動態規劃通常用於存在大量重疊子問題的情況。在動態規劃中，一旦計算出一個子問題的解，就會將其存儲起來，以便在再次需要計算該問題時直接使用。相反，貪心算法並不考慮子問題的重疊。 - 最優子結構
動態規劃和貪心算法都需要問題具有最優子結構性質。這意味著可以通過子問題的最優解來得到原問題的最優解。 - 選擇性質
貪心算法依賴於選擇性質，即局部最優選擇能導致全局最優解。貪心算法在每個決策階段都會做出在當前看來是最好的選擇，不考慮這個選擇可能會對未來的決策產生什麼後果。而動態規劃則會評估所有可能的選項，並選擇最優的一個。 - 解決問題的方式
貪心算法通常是一種迭代的方法，每一步都選擇當前最優的解，而不需要考慮以前或者未來的決策。而動態規劃通常需要創建一個表格來存儲和查找所有的子問題解決方案。
如何判斷一個問題是用動規還是貪心來解？#
- 確定問題是否是一個優化問題
例如最小路徑問題，最大利潤問題等，這些問題可能需要動態規劃或貪心算法。 - 看是否存在 "最優子結構" 的特性
最優子結構意味著問題的最優解可以由其子問題的最優解構成。如果存在這樣的結構，那麼可能適合用動態規劃或貪心算法解決。 - 對於動態規劃，還要看問題是否有 "重疊子問題"
即是否存在多個問題共享同一子問題的情況，且重複計算會導致效率低下。這種情況常常適合用動態規劃。 - 判斷問題是否滿足 "貪心選擇性質"
即局部最優選擇能導致全局最優解。也就是說，你可以一步一步地做出最優的選擇，而不需要考慮整體。如果存在這樣的特性，可能適合使用貪心算法。 - 需要考慮問題的複雜性和所需的解決速度
貪心算法通常更簡單，計算速度也更快，但它並不總是能找到問題的最優解。相反，動態規劃雖然可能更複雜，計算速度也可能較慢，但它更可能找到問題的最優解。 - 考慮問題的規模
對於大規模問題，動態規劃可能需要大量的內存來存儲子問題的解，這可能是不可行的。
如何拆解子問題？#
拆解子問題是解決動態規劃和貪心算法問題的關鍵步驟。
記住，拆解子問題需要一些練習和經驗。不同的問題可能需要不同的方法來拆解子問題，這需要時間和耐心來學習。
- 確定最優子結構
嘗試找到一個更小的、簡化的版本或子集的問題，這個子問題的解決方式應當與原問題相似。這種子問題的最優解會幫助我們構建原問題的最優解。 - 子問題的定義
你需要定義清楚子問題是什麼。比如在最短路徑問題中，子問題可能是從起點到達中間某個點的最短路徑。 - 狀態轉移方程
這個方程表達了子問題之間是如何相互關聯的。狀態轉移方程會告訴你如何從已經解決的子問題推導出當前子問題的解。 - 邊界條件
找出最簡單的子問題，它們的解是顯而易見的。比如在斐波那契數列問題中，最初的兩個數就是邊界條件。 - 子問題之間的關係
在動態規劃中，子問題通常會重疊，即某些子問題會在求解其他子問題時再次出現。這時就可以利用已經求解過的子問題的答案，避免重複計算。
5 個典型的動態規劃問題#
-
- 斐波那契數列：給定 n，計算斐波那契數列的第 n 項。
-
- 鋼條切割：給定一個長度和價格的列表，求出如何切割鋼條可以得到最大的總價值。
-
- 最長公共子序列：給定兩個字符串，找到最長的公共子序列。
-
- 0-1 背包問題：給定一組物品，每個物品都有自己的重量和價值，確定在不超過背包重量限制的情況下，如何選擇物品以最大化總價值。
-
- 矩陣鏈乘法：給定一個矩陣鏈，我們需要決定最優的乘法順序，以最小化總的乘法次數。
5 個典型的貪心算法問題#
-
- 活動選擇問題：給定一組活動，每個活動都有開始時間和結束時間，我們需要選擇最大數量的活動，使得這些活動之間沒有時間上的衝突。
-
- 霍夫曼編碼：用於數據壓縮的一種算法，需要構建一個最優的霍夫曼樹。
-
- Dijkstra 算法：用於求解圖的單源最短路徑問題。
-
- 分數背包問題：與 0-1 背包問題類似，但是物品可以被分割，我們需要決定如何選擇和分割物品以最大化總價值。
-
- Kruskal 算法和 Prim 算法：用於求解圖的最小生成樹問題。