CS

一、分治法 分治法，簡而言之就是分而治之，把複雜的問題分成兩個或更多個相似或相似的子問題，直到子問題可以直接求解，最後再將子問題的解做合併。 三步驟：Divide、Conquer、Merge 以 pseudo code 來表示大概像： void func(collection set) { // 子問題求解 if (base_case) { // 根據要求將子問題解合併成母問題解 do_something return; } // 將母問題分解成子問題 for (collection subset : set) { func(subset); } } graph LR; 母問題-->子問題1; 母問題-->子問題2; subgraph Divide 子問題1-->最小子問題1; 子問題1-->最小子問題2; 子問題2-->最小子問題3; 子問題2-->最小子問題4; end subgraph Conquer 最小子問題1-->最小子問題解1; 最小子問題2-->最小子問題解2; 最小子問題3-->最小子問題解3; 最小子問題4-->最小子問題解4; end subgraph Merge 最小子問題解1-->合併; 最小子問題解2-->合併; 最小子問題解3-->合併; 最小子問題解4-->合併; end 合併-->母問題解 舉例說明，河內塔遊戲： 河內塔是由三根桿子以大小不同碟片所組成的遊戲，僧人一次可以從一根桿子移動一個碟片到另一根桿子，但是小的碟片若放憂大的碟片下面會使得小的碟片裂開(也就是碟片只能由上而下從小排到大)，試問將一座塔從一根桿子完整的移動到另一根桿子需要移動多少次。 思考上面的情形，以三個碟片為例，若我們要從 A 到 C 移動一座塔，我們可以將之分解成「如何把上面兩個碟片移動到 B」，因為剩下的一個大碟片，可以很簡單的從 A 移動到 C。也就是說 f3(A->C) = f2(A->B) + f1(A->C) + f2(B->C)。 再更進一步，f2(A->B) 和 f2(B->C) 其實就是移動兩個碟片到另一座塔，所以可以分解成 f2(A->C) = f1(A->B) + f1(A->C) + f1(B->C)，至此，我們已經把 f3 都分解成可以代表一次移動的最小子問題的解 f1 了： graph TD; A[f3,A->C] B[f2,A->B] C[f1,A->C] D[f2,B->C] E[f1,A->C] F[f1,A->B] G[f1,C->B] H[f1,B->A] I[f1,B->C] J[f1,A->C] A-->B A--->C A-->D B-->E B-->F B-->G D-->H D-->I D-->J 故我們可以以數學方式證明：...

一、貪心演算法 是一種在每一步都採前當下看起來最好的選擇的一種策略。 由於是當下看起來最好的選擇，故也有可能選到錯的路線，導致最終的答案不是最佳解。 先舉個生活中常見的例子： 今天小明的撲滿裡存滿了大大小小的1塊、5塊跟10塊，今天小明打算要要幫撲滿瘦身，令它的重量降低，那麼小明可以到銀行換鈔，將幣值小、重量重的硬幣集結起來換成幣值大、重量輕的紙鈔。 用貪心演算法的思維，我們一定是從幣值大的 1000 開始換起，再來 500、100、50、10，以此類推，有多少換多少。 // vector<int>& nums = {1000, 500, 100, 50, 10, 5, 1}; vector<int> coinChange(vector<int>& nums, int money) { vector<int> res(nums.size(), 0); for (int i = 0; i < nums.size(); i++) { res[i] += (money / nums[i]); money %= nums[i]; } return res; } 但若我們新增了一個幣值是 23，那麼上面這個思路就有可能會導致錯誤。 貪心演算法的特點 直覺且快速 通常不是最佳的 需要會被要求證明 always stays ahead：跑者每個時間點都在第一名，最後結果會是第一名 用歸納法證明。 exchange argument 用反證法，找到原解的 inversions，並作交換，證明交換後並不影響最佳解。 二、貪心演算法的應用 0. 核心思維 貪心演算法是從某一個初始狀態出發，每次通過選取區域性最優解向目標前進，並最終期望取得整體最優解的一種演算法。由這個定義可知，貪心選擇標準就是選擇當前最好的決策，貪心演算法根據這個標準進行決策，將原問題變成一個相似但規模更小的子問題，而後每一步選出來的一定是原問題整體最優解的一部分。 如果一個問題貪心後只剩下一個子問題且有最優子結構，那麼該問題就可以使用貪心演算法。當一個問題的整體最優解包含其子問題的最優解時，我們稱次問題具有最優子結構性質。 解題一般步驟 設計資料結構並找規律 進心貪心猜想 正確性證明(歸納法證明或是列舉反例進行反證) 實現程式碼 1....

一、暴力演算法 暴力演算法就是枚舉法，試想今天有一個行李箱的密碼鎖為四個一組，但你又忘記密碼，那要怎麼辦？你會試著從 0000 轉到 9999 共 10000 種組合都試過，必定會找出密碼，把所有可能都枚舉過一遍，遍是暴力演算法。 暴力演算法可以應用於很多問題，包含數論、樹、圖論等等，而暴力演算法的重點在於枚舉所有可能，以樹來說就是樹的遍歷。 舉例來說： Leetcode 1. Two Sum 給定一個數列，找數列中任兩個數的和為 target，回傳兩個數的索引值。 在還沒有認識任何資料結構之前，我們能想到最簡單的方法就是遍歷整個數列，用兩個指標 i 與 j，各指向一個數，將所有可能檢查過一遍，直到找到目標。 vector<int> twoSum(vector<int>& nums, int target) { for (int i = 0; i < nums.size() - 1; i++) for (int j = i + 1; j < nums.size(); j++) if (nums[i] + nums[j] == target) return {i, j}; return {-1, -1}; } 以上例來說，用暴力破解法求解時，求兩數和的時候，我們需進行兩個維度的 for-loop 迴圈來求解。若進一步到三數和、四數和、五數和時，我們會發現，維度會隨著多少個數字和增加。也就是三數和為 3 個迴圈，四數和為 4 個迴圈，以此類推。 以 複雜度分析 Algorithmic complexity / Big-O / Asymptotic analysis來分析，也就相當於 k 數和的時間複雜度為 \(O(n^k)\)，這個增長是相當恐怖的。 暴力演算法的特點...

algorithm <algorithm> 定義了專為元素集合設計的函式。 元素集合包含可以被迭代器或指標存取的一系列元素，例如陣列或 STL container。但且注意，演算法只會透過迭代器去操作容器中的值，並不會更改其結構或是大小。 一、函式 1. 無修改值的操作 all_of bool all_of(Iterator first, Iterator last, UnaryPredicate pred) 檢查是否全部的元素都符合判斷式。 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ vector<int> arr1 = {1,2,3,4,5}; vector<int> arr2 = {1,3,5,7,9}; vector<int> arr3 = {2,4,6,8,10}; auto isodd = [](int x)->bool{ return x%2; }; cout << all_of(arr1.begin(), arr1.end(), isodd) << endl; // 0 cout << all_of(arr2.begin(), arr2.end(), isodd) << endl; // 1 cout << all_of(arr3.begin(), arr3....

一、動態規劃的思考藝術 動態規劃其實就是一種暴力枚舉的優化，在暴力枚舉的過程中有著大量的重複，藉由「備忘錄(memoization)」的方式做到剪枝(pruning)來達到優化的一種演算法。 舉例來說： Leetcode 62. Unique Paths 機器人由左上走到右下角星星有幾種走法，其中機器人只能選擇往右走或往下走。 試想機器人從 (1,1) 走到 (m,n) 的不同路徑中，可見有大量的重複，比如過程中有一點 (i,j)，其 (1,1) 走到 (i,j) 有 k 條不同路徑，麼那對於任何一條固定 (i,j) 到 (m,n) 的路徑，都需走 k 遍來模擬。 但其實我們不必關心具體的走法，我們只關心狀態，也就是走法的數目。 同理，我們若知道 (i,j) 到 (m,n) 共有 t 條不同的路徑，那麼 (1,1) -> (i,j) -> (m,n) 的不同路徑總數就是 k*s。 我們知道最左邊那欄與最上面那列都只有可能有一種路徑可以走，又每一格的路徑來自於上方與左方的和： sum of (i,j) = sum of (i-1,j) + sum of (i,j-1) \(\begin{array}{|c|c|c|c|c|c|c|}\hline \text{1}&\text{1}&\text{1}&\text{1}&\text{1}&\text{1}&\text{1}\\\hline \text{1}&\text{2}&\text{3}&\text{4}&\text{5}&\text{6}&\text{7}\\\hline \text{1}&\text{3}&\text{6}&\text{10}&\text{15}&\text{21}&\text{28}\\\hline \end{array}\) 寫成程式碼就是 int uniquePaths(int m, int n) { vector<vector<int>> dp(m+1, vector<int>(n+1,0)); for (int i = 1; i <= m; i++) // 將第一列填成 1 dp[i][1] = 1; for (int j = 1; j <= n; j++) // 將第一欄填成 1 dp[1][j] = 1; for (int i = 2; i <= m; i++) { // 將剩下的格子填完 for (int j = 2; j <= n; j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m][n]; } 注意填格子的順序是有一定的限制的，必須要確保相關聯的子問題已經處理過。 動態規劃 由上例我們可以發現，原本的問題可以拆解成更小的問題(從 (1,1)->(m,n) 變成從 (1,1)->(i,j) 和從 (i,j)->(m,n))。 我們令 f(i,j) 表示從 (1,1)->(i,j) 的不同路徑數，則我們可以得到轉移方程式 f(i,j)=f(i-1,j)+f(i,j-1)。 我們發現，想求出 f(i,j) 只需要知道幾個更小的 f(i',j')。我們將 f(i',j') 稱為子問題。 我們捨棄冗餘的訊息(具體的走法)，只記錄對解決問題有幫助的結果。 動態規劃的兩大特點(適用前提) 無後效性 一旦 f(i,j) 確定，就不用關心我們如何計算出 f(i,j) 想要確定 f(i,j)，只需要知道 f(i-1,j) 和 f(i,j-1) 的值，而至於它們是如何算出來的，對當前或之後的任何子問題都沒有影響。 過去不依賴未來，未來不影響過去。 最優子結構 f(i,j) 的定義就已經蘊含了最優。 大問題的最優解可以由若干個小問題的最優解推出。(max, min, sum…) DP 能適用於：能將大問題拆成若干小問題，滿足無後效性、最優子結構性質。 以下介紹幾種刷題會遇到的動態規劃套路： 二、動態規劃框架 1....