25815: 回文字符串

http://cs101.openjudge.cn/practice/25815/

给定一个字符串 S ，最少需要几次增删改操作可以把 S 变成一个回文字符串？

一次操作可以在任意位置插入一个字符，或者删除任意一个字符，或者把任意一个字符修改成任意其他字符。

输入

字符串 S。S 的长度不超过100, 只包含'A'-'Z'。

输出

最少的修改次数。

样例输入

ABAD

样例输出

来源

hihoCoder

这是一个经典的动态规划问题，可以使用动态规划来解决这个问题。定义一个二维数组 dp，其中 dp[i][j] 表示将字符串 S 的子串 S[i...j] 变成回文串所需要的最小操作次数。

使用状态转移方程来填充 dp 数组：

如果 S[i] == S[j]，那么 dp[i][j] = dp[i+1][j-1]，因为两端的字符已经相等，不需要进行任何操作。
如果 S[i] != S[j]，那么 dp[i][j] = min(dp[i+1][j], dp[i][j-1], dp[i+1][j-1]) + 1，可以选择删除 S[i] 或 S[j]，或者将 S[i] 或 S[j] 修改为另一个字符。

最后，dp[0][n-1] 就是答案，其中 n 是字符串 S 的长度。

以下是使用 Python 实现的代码：

python

def min_operations(s):
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for i in range(n-1, -1, -1):
        for j in range(i+1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1]
            else:
                dp[i][j] = min(dp[i+1][j], dp[i][j-1], dp[i+1][j-1]) + 1
    return dp[0][n-1]

s = input().strip()
print(min_operations(s))

这段代码首先读取输入的字符串，然后调用 min_operations 函数计算并打印出将字符串变成回文串所需要的最小操作次数。

25815: 回文字符串 ​

25815: 回文字符串