POJ1159，动态规划经典题目，很适合初学者入门练手。 求：为了使字符串左右对称，应该插入的最小字符数目。 设字符串为S1 S2 S3 … Sn. 这个字符串有n个字符，根据DP的基本思路，减少问题规模。如果S1和Sn匹配，则只关心S2 S3 …Sn-1，就这样问题规模减少了。如果S1和Sn不匹配，那就有两种办法。 方法1：加入S1’，字符串成S1S2 S3 … Sn S1’，则问

最最基础的LCS问题～～～ 关于LCS有很多很多的解释： 觉得这四个说的蛮好的：觉得这四个说的蛮好的： http://blog.chinaunix.net/uid-26548237-id-3374211.html http://blog.csdn.net/yysdsyl/article/details/4226630 http://blog.csdn.net/v_july