※ [本文转录自 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 全满，由此拿掉多加的字符即可