部分恕删，另外在这边告知一下原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大耐心提出反例与盲点）
以上是我查过资料后的一些想法，还请大家有其他想法尽量提出、指正，
感谢！