插入最少字符构成回文

今天在微信上看到的。要多思考，学会这种动态规划的思路。

#题目 给定字符串，插入字符使其构成回文。求最少插入字符的数量。

#分析 考虑长度为n的字符串str整体： 1.若str[0] == str[n-1]，则问题转变为求str[1,n-2]，插入最少字符，得到回文。 2.若str[0] != str[n-1]，则添加一个字符转化为情况1，即插入str[0]或者str[n-1]。分别转化为求str[1,n-1]或者str[0,n-2]。

所以有递归：$$fmi(str, l, h) = (str[l] == str[h]) ? fmi(str, l+1, h-1) : (min(fmi(str, l+1, h), fmi(str, l, h-1))+1)$$

#示例代码

int fmiDP(char str[], int n) {
	//二位数组保存子问题的解
	int table[n][n], l, h, gap;
	memset(table, 0, sizeof(table));
	for (gap = 1; gap < n; ++ gap) {
		for (l = 0, h = gap; h < n; ++l, ++h) {
			table[l][h] = (str[l] == str[h]) ? table[l+1][h-1] : (min(table[l][h-1], table[l+1][h]) + 1);
		}
	}
	return table[0][n-1];
}