uva10739经典动态规划
题目
给出一个字符串,长度小于一千。你可以执行三种操作:
- 删除一个字符
- 增加一个字符
- 修改一个字符
问,最少执行多少次操作可以使原字符串变成回文字符串。
解题思路
$dp[i][j]$表示将区间$[i,j]$修改成回文串的最小花费。
由于$dp$的性质,当求$dp[i][j]$时,$dp[i+1][j-1]$、$dp[i+1][j]$、$dp[i][j-1]$都已经知道了。
如果$a[i]==a[j]$,那么$dp[i][j]=dp[i+1][j-1]$
否则,也就是$a[i]!=a[j]$,有五种方案:
- 删除$a[i]$,有$dp[i][j]=dp[i+1][j]+1$
- 删除$a[j]$,有$dp[i][j]=dp[i][j-1]+1$
- 增加一个和$a[j]$相同的字符$a[i]$,有$dp[i][j]=dp[i+1][j]+1$
- 增加一个和$a[i]$相同的字符$a[j]$,有$dp[i][j]=dp[i][j-1]+1$
- 将$a[i]$修改成$a[j]$ 或 将$a[j]$修改成$a[i]$,有$dp[i][j]=dp[i+1][j-1]+1$
可以发现删除和增加操作转移方程一样,因此总共三种转移方式。
代码
1 |
|