筆記

連通與路徑連通 一個由 [a,b] 映射到 metric space M 的函數 f ，如果 [a,b] 中所有的收斂序列 tk -> t，經過 f 也會收斂 f(tk) -> f(t)，則我們說 f 是一個連續函數。 一個集合中，若 任意兩點皆可找到一個落在集合中的連續函數相連 ，則稱此集合 路徑連通( path connected ) 。 若兩開集合 U、V 符合以下性質，則說他們將集合 A 分開： (1) U、V 聯集包含 A，(2) U、V 與 A 皆有交集，(3) U、V、A 交集為空。 若一個集合 不能被兩個開集合分開 ，則我們說此集合 連通( connected )。 任意區間 [a,b] 都是連通的。 不可能存在兩個非空無交集的閉集合，包住一個閉區間 [a,b]。 路徑連通必連通。 若 S 是一個連通集合，且 T 被夾在 S 和 S 的 closure 之間，則 T 亦連通。 一個連通集合通過連續函數作用仍然連通。 實數的連通子集 <=> 一個區間。 在 Rn 中的一個連通開集合必路徑連通。

動態規劃 生產線問題，到達每一關最短的時間，可以由上一關的最短時間加上多的時間比較而知，由此遞迴需時O(2^n)。使用動態規劃只需 O(n)。 具有以下兩性質者可以利用動態規劃： optimal substructure：可以使用遞迴。 Overlapping Subproblems：遞迴時會重複遇到同樣的問題。 m*n 矩陣和 n*o 矩陣相乘需要運算 O(mno) 次，得到 m*o 矩陣。 因此一長串矩陣相乘，有不同的組合、括括號的方式，在最後一次相乘的各種方式中找出最小值，就可得到最快的方法，藉此可遞迴解決此問題。 在每一種方式中，計算兩子問題的最快方法再加上最後一次相乘的時間，即可算出某種括號方式的最快時間。但直接遞迴需要用到 O(3^n) 的時間。使用動態規劃只需 O(n^3)。 一個字串的 subsequence 是指由原字串剔除(沒有剔除也算在內)掉某些字元後剩下的字串，兩個字串的 longest common subsequence 是指兩個字串相同的子字串中最長的那些字串。 兩個字串的字尾如果相同，那字尾一定在 LCS 之中，且 LCS 是兩個字串都剪掉字尾後的 LCS 再加上字尾。若是字尾不相同，那麼 LCS 要嘛不包含第一個字串的字尾，要嘛不包含第二個字串的字尾，利用此性質可得一遞迴解法，時間 O(2^(m+n))，使用動態規劃只需 O(mn)。 電子字典中，每一個字被查詢的機率不同，每個錯字區間也是如此，希望設計出一個搜尋樹(最佳二元搜尋樹)，使得平均搜尋的時間最短，在一個搜尋樹中，搜尋時間的期望值即每個字或區間的機率乘上其所在的深度再相加，可以發現最佳搜尋樹的兩個子樹也要是最佳搜尋樹，而一棵樹的搜尋時間為整棵樹的機率加上兩個子樹的搜尋時間。藉此可得出一遞迴方法計算所有可能的搜尋樹得出最佳解。 使用動態規劃，由只有一個元素的搜尋樹開始，計算搜尋時間，層層疊上計算出所有可能的子搜尋樹的最佳解，最後即可得完整的最佳搜尋樹。