# DP 跟 divide and conquer 差在哪
分而治之法 (Divide and Conquer) 如果問題很大，我們就把問題分解成較小的子問題，然後分別解決這些子問題。一旦所有的子問題都解決了，我們就把所有子問題的解決方案組合起來，找到大問題的解決方案。分治法的限制是子問題應該與原問題屬於同一類型。例如，如果主要問題是排序，那麼子問題也應該是排序。分治法的策略本質上是遞迴的。
動態規劃 (Dynamic Programming) 則是將優化問題分解成更簡單的子問題，並存儲每個子問題的解決方案，以便每個子問題只需要解決一次。一旦所有的子問題都解決了，我們就將每個子問題的結果連接起來，找到初始問題的解決方案。
當我們看到一個遞迴解決方案對於相同的輸入有重複的調用時，我們可以使用動態規劃來優化它。
這種方法的想法是簡單地存儲子問題的結果，這樣我們就不需要在以後需要時重新計算它們。
例如，如果我們寫出斐波那契數列的簡單遞迴解決方案，我們會得到指數時間複雜度，如果我們通過存儲子問題的解決方案來優化它，時間複雜度就會從指數級降低到線性級。
# Quick sort
快速排序（Quick Sort）是一種常用的排序算法，它通過選擇一個基準元素，將數列分割成兩個子數列，並將比基準元素小的元素放在基準元素的左邊，比基準元素大的元素放在基準元素的右邊，然後對子數列進行遞迴排序，最終實現整個數列的排序。
下面是一個簡單的範例來說明快速排序的過程：
假設我們要對數列 [7, 2, 1, 6, 8, 5, 3] 進行排序。
- 選擇基準元素：從數列中選擇一個基準元素，通常選擇第一個或最後一個元素。在這個例子中，我們選擇第一個元素 7 作為基準元素。
- 分割操作：將數列重新排列，小於基準元素的元素放在左邊，大於基準元素的元素放在右邊。在這個例子中，我們將小於 7 的元素放在左邊，大於 7 的元素放在右邊，得到 [2, 1, 6, 5, 3, 7, 8]。
- 遞迴排序：對左右兩個子數列進行遞迴排序，重複上述步驟。在這個例子中，我們對左子數列 [2, 1, 6, 5, 3] 和右子數列 [8] 進行遞迴排序。
- 合併結果：將排序後的左子數列、基準元素和排序後的右子數列合併在一起。在這個例子中，最終得到排序後的數列 [1, 2, 3, 5, 6, 7, 8]。
總結：
快速排序通過選擇基準元素，將數列分割成兩個子數列，並對子數列進行遞迴排序，最終實現整個數列的排序。它的核心操作是分割，將小於基準元素的元素放在左邊，大於基準元素的元素放在右邊。快速排序是一種高效的排序算法，平均時間複雜度為 O (nlogn)，但在最壞情況下可能達到 O (n^2)。
