※ [本文轉錄自 Math 看板 #1GeQZ_sR ]
作者: Murasaki0110 (Paradise Lost) 看板: Math
標題: [Algo] Optimal substructure
時間: Tue Nov 13 09:57:18 2012
※ [本文轉錄自 Grad-ProbAsk 看板 #1GdbXbbS ]
作者: Murasaki0110 (Paradise Lost) 看板: Grad-ProbAsk
標題: [理工] [Algo] Optimal substructure
時間: Sat Nov 10 21:36:35 2012
想請問下列兩個問題
若用DP解的話, Optimal substructure該找什麼
1.給任意一個string, 要把它變成迴文, 最少需要幾次insert?
ex. abcd

第一題不能插成abbccd嗎？這樣好像只要兩次阿阿對不起眼殘= =…

第一題 似乎可以算出S和revert(S)的最長共同子序列把字串長度減最長共同子序列長 應該就是答案仔細想一下 確定方法是對的結果

樓上作法是正確的，可以證明。第二題是經典Bridge and torch problem，wiki上也有。

我也覺得是 S 和 reverse(S) 的 LCS 的作法正確，但如何證？

LCS>=OPT: 補上沒有對到的字元OPT>=LCS: 迴文時 LCS 全滿，由此拿掉多加的字元即可