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

本文出自：http://blog.csdn.net/svitter 原题：http://poj.org/problem?id=1141 题意：输出添加括号最少，并且使其匹配的串。 题解： dp [ i ] [ j ] 表示添加括号的个数， pos[ i][ j ] 表示 i ， j 中哪个位置分开，使得两部分分别匹配。 pos [ i ][ j ] 为-1的时候，说明i, j 括号匹

POJ1141，brackets sequence，括号比配的问题。这题与上面两题有点像，有了上面两题的基础，分析此题也不难。好了，还是看题吧。 求：为了使原来的括号序列匹配，需求加入了最少括号数，而且要知道具体怎么加括号。 因为这题需要打印最终的匹配结果，所以在用DP的时候要多记录一些信息，以方便打印。 设原括号序列为S1 S2 … Sn。 如果S1和 Sn匹配，则相当于求S2