CS

一、回溯法 回溯法與 dfs 相當類似，本質上都是暴力窮舉的演算法，但細微的差異在於： dfs 在遍歷節點。 backtracking 在遍歷樹枝。 站在回溯樹上的一個節點，需要考慮的只有三件事情： 路徑 選擇 終止條件 以全排列問題([Leetcode] 46. permutation)來舉例 全排列問題即給定一組數組 nums，需返回這些數字的所有排列組合，舉例來說，給定一個數組 nums = [1,2,3]，那麼它可能的排列會有： [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] 對應上圖的回溯樹來看，我們在每個樹的節點，都會面臨一次決策，站在樹的根時，相當於我們要選擇排列的第一位，而我們有三個選擇，即 1 或 2 或 3。若我們的第一位選擇了 1，代表我們選擇了 \(\text{x}_1=1\) 的路徑，故接下來我們的選擇只剩下兩個，即 2 或 3。當我們繼續往下做，直到子葉節點時，代表我們已經沒有選擇可選，此時就是我們的終止條件。 回憶我們在二叉樹中練習過前序、中序、後序的思維，前序與後序代表我們在遍歷節點前與後的時間點，而在回溯法，這兩個時間點，各自代表了 將選擇加入路徑 從路徑中撤銷選擇 用二叉樹程式碼來說明即： void traverse(TreeNode* root){ if (!root) return; // preorder: do option traverse(root->left); traverse(root->right); // postorder: retrieve option } N-ary 樹： class Node{ int val; vector<Node*> children; }; void traverse(Node* root){ if (!...

一、貪心演算法 是一種在每一步都採前當下看起來最好的選擇的一種策略。 由於是當下看起來最好的選擇，故也有可能選到錯的路線，導致最終的答案不是最佳解。 先舉個生活中常見的例子： 今天小明的撲滿裡存滿了大大小小的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....