首先,让我们考虑一个低效的递归解决方案:
假设字符串是格式aSb,where a和b是字母,S是子字符串.
如果a==b,那么f(aSb) = f(S).
如果a!=b,那么你需要添加一个字母:a在最后添加一个,或b在前面添加一个.我们需要尝试两者,看看哪个更好.所以在这种情况下,f(aSb) = 1 + min(f(aS), f(Sb)).
这可以使用递归函数来实现,该函数将需要指数时间才能运行.
要提高性能,请注意只能使用原始字符串的子字符串调用此函数.只有O(n ^ 2)个这样的子串.因此,通过记忆这个函数的结果,我们减少了O(n ^ 2)所花费的时间,代价是O(n ^ 2)空间.
| 归档时间： |
|
| 查看次数： |
1261 次 |
| 最近记录： |