# DP 跟 divide and conquer 差在哪

分而治之法 (Divide and Conquer) 如果問題很大,我們就把問題分解成較小的子問題,然後分別解決這些子問題。一旦所有的子問題都解決了,我們就把所有子問題的解決方案組合起來,找到大問題的解決方案。分治法的限制是子問題應該與原問題屬於同一類型。例如,如果主要問題是排序,那麼子問題也應該是排序。分治法的策略本質上是遞迴的。

動態規劃 (Dynamic Programming) 則是將優化問題分解成更簡單的子問題,並存儲每個子問題的解決方案,以便每個子問題只需要解決一次。一旦所有的子問題都解決了,我們就將每個子問題的結果連接起來,找到初始問題的解決方案。

當我們看到一個遞迴解決方案對於相同的輸入有重複的調用時,我們可以使用動態規劃來優化它。

這種方法的想法是簡單地存儲子問題的結果,這樣我們就不需要在以後需要時重新計算它們。

例如,如果我們寫出斐波那契數列的簡單遞迴解決方案,我們會得到指數時間複雜度,如果我們通過存儲子問題的解決方案來優化它,時間複雜度就會從指數級降低到線性級

# Quick sort

快速排序(Quick Sort)是一種常用的排序算法,它通過選擇一個基準元素,將數列分割成兩個子數列,並將比基準元素小的元素放在基準元素的左邊,比基準元素大的元素放在基準元素的右邊,然後對子數列進行遞迴排序,最終實現整個數列的排序。

下面是一個簡單的範例來說明快速排序的過程:

假設我們要對數列 [7, 2, 1, 6, 8, 5, 3] 進行排序。

  1. 選擇基準元素:從數列中選擇一個基準元素,通常選擇第一個或最後一個元素。在這個例子中,我們選擇第一個元素 7 作為基準元素。
  2. 分割操作:將數列重新排列,小於基準元素的元素放在左邊,大於基準元素的元素放在右邊。在這個例子中,我們將小於 7 的元素放在左邊,大於 7 的元素放在右邊,得到 [2, 1, 6, 5, 3, 7, 8]。
  3. 遞迴排序:對左右兩個子數列進行遞迴排序,重複上述步驟。在這個例子中,我們對左子數列 [2, 1, 6, 5, 3] 和右子數列 [8] 進行遞迴排序。
  4. 合併結果:將排序後的左子數列、基準元素和排序後的右子數列合併在一起。在這個例子中,最終得到排序後的數列 [1, 2, 3, 5, 6, 7, 8]。

總結:
快速排序通過選擇基準元素,將數列分割成兩個子數列,並對子數列進行遞迴排序,最終實現整個數列的排序。它的核心操作是分割,將小於基準元素的元素放在左邊,大於基準元素的元素放在右邊。快速排序是一種高效的排序算法,平均時間複雜度為 O (nlogn),但在最壞情況下可能達到 O (n^2)。