部分恕刪，另外在這邊告知一下原po
我在我這篇標題有雞婆加上學校年份，以供未來有需要的人也可以搜到
還請原po見諒
※ 引述《leexu3 (LEE)》之銘言：
: 成大的99年Checkboard
: https://imgur.com/a/rLdeR
: 1.寫不出code 雖然感覺很明顯對 ＝＝
不知道這樣寫pseudo code可不可以：
// size: 記錄大小為2^n * 2^n之checkerboard的n
function board_cover(board bd, size n):
// 若只剩大小為2 * 2之checkerboard，
// 根據我們的做法，必定當中已有1 * 1的square不可cover，
// 等同被移除一塊square
if size == 1:
將一個tromino覆蓋剩餘區域;
return;
else:
將大小為2^n * 2^n之checkerboard劃分為4塊大小為2^n-1 * 2^n-1的board;
分別標記為b1, b2, b3, b4;
判斷該4塊中哪塊board有存在1 square不可cover;
在2^n * 2^n之board的中心覆蓋上一個tromino，其覆蓋的區域各有1 square位在
其它「原不存在不可cover的1 square」的3大塊board;
// 如此一來，此時4大塊2^n-1 * 2^n-1的board各有1 square不可cover
// 遞迴對這4大塊board再去填滿tromino
board_cover(b1, n - 1);
board_cover(b2, n - 1);
board_cover(b3, n - 1);
board_cover(b4, n - 1);
return;
我覺得應該這樣大概寫出做法就可以了，可以的話再畫圖示意，
這樣閱卷老師應該會接受吧QwQ？
資料結構還有其他細節小弟我覺得應該不算此題重點，所以就沒詳述了
（用array存board、中心的index、如何判斷哪一塊存在不可cover的square）
若概念有問題或哪邊還可以寫得更不冗長，還請各位不吝指點，感謝！
: 成大103
: https://imgur.com/a/iFpp4
: Prove that "the longest increasing subsequence problem" can be reduced
: to "the edit distance problem"
: 兩個演算法我會 但不知道怎麼reduced 感覺就是有讀沒有通
: 想上來請益各位 謝謝！
不好意思這題最後的細節我也不清楚
（有了min cost的編輯序列，該如何用這序列去求出LCS，也就是LIS），
以下前段主要來自於林立宇老師的演算法講義
假設LIS中input sequence為X = (7, 4, 1, 2, 6)
對X排序，可得sequence Y = (1, 2, 4, 6, 7)，則求LIS(X)又等同求LCS(X, Y)
再來看Edit distance problem(ED)
定義edit operation及其cost：
1. substitution，Cs = 2
2. insertion，Ci = 1
3. deletion，Cd = 1
題外話，我覺得「替代」的操作在此題reduce中似乎沒用到？（概念有錯還請指正）
接著是min edit cost與LCS length的關係
首先LIS(X) = LCS(X, Y) = (1, 2, 6)
假設為ED(X, Y)為要將X編輯成Y的min cost，
等同於在X中delete非LIS的元素（刪x1, x2的7, 4），接著同時對照Y
在X對應的位置insert被刪掉的元素（在2, 6間插4、在最尾端插7）
由上述例子可知，假設X的元素數量（|X|）為n，LCS元素數為|LCS(X, Y)|
則ED(X, Y) = 2 * (|X| - |LCS(X, Y)|)
所以當若給一input sequence X（也同樣是欲求LIS的X），
排序X得Y，接著先找出具有min cost的編輯序列，
再來我不太理解的是，該如何從這些insert、delete的operation中，
求出X和Y的LCS，也就是X的LIS呢？
林立宇老師的講義上只寫「欲求LIS(X)」，只需在過程中額外記錄一些編輯的程序即可
假設X = (4, 1, 2)，Y = (1, 2, 4)
min cost of edit sequence是從X刪除x1，插入y3到X，
那我們該如何從這兩個operation中，得知X的LIS就是(x2, x3)，也就是1, 2呢？
小弟的猜想是，最後的編輯序列求出後，
「只執行」編輯序列中delete的操作，一旦編輯序列中沒有delete，就output X的內容
值得一提的是，將substitution 視為等同 delete 再 insert，所以成本我設為相同
（2 = 1 + 1）
當最後有了編輯序列後，我將每個substitution都以「delete + insert」的操作取代
或者，一開始直接將substitution的cost設為無限大，
如此一來必不會有substitution的操作出現，即可正確輸出
（感謝FARXIS大耐心提出反例與盲點）
以上是我查過資料後的一些想法，還請大家有其他想法盡量提出、指正，
感謝！