01159: Palindrome

dp, http://cs101.openjudge.cn/practice/01159/

A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome.

As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.

输入

Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from 'A' to 'Z', lowercase letters from 'a' to 'z' and digits from '0' to '9'. Uppercase and lowercase letters are to be considered distinct.

输出

Your program is to write to standard output. The first line contains one integer, which is the desired minimal number.

样例输入

5
Ab3bd

样例输出

来源

IOI 2000

问题是需要找到将给定字符串转换为回文所需的最少插入字符数。回文是指从左到右和从右到左读都相同的字符串。可以通过动态规划的方法来解决这个问题，具体思路是计算原字符串与其反转字符串的最长公共子序列（LCS），然后用原字符串的长度减去LCS的长度，得到所需插入的最少字符数。

方法思路

问题分析：回文的结构具有对称性，利用动态规划来找到原字符串与其反转字符串的最长公共子序列。这个子序列的长度即为原字符串中最长回文子序列的长度。
动态规划：使用一维数组优化空间复杂度，将二维动态规划数组转换为两个一维数组，交替使用以节省空间。
复杂度分析：时间复杂度为O(n²)，空间复杂度为O(n)，其中n是字符串的长度。

Python, 4564ms AC.

python

def min_insertions_to_palindrome(n, s):
    t = s[::-1]
    dp = [0] * (n + 1)
    
    for i in range(n):
        current_char = s[i]
        prev_prev = 0
        for j in range(1, n + 1):
            current = dp[j]
            if current_char == t[j - 1]:
                dp[j] = prev_prev + 1
            else:
                if dp[j - 1] > dp[j]:
                    dp[j] = dp[j - 1]
            prev_prev = current
    
    return n - dp[n]

# 读取输入
n = int(input())
s = input().strip()

# 计算并输出结果
print(min_insertions_to_palindrome(n, s))

PyPy3, 404ms. 通过将核心逻辑封装到函数中，提升代码的执行速度。

python

n = int(input())
s = input().strip()
t = s[::-1]

dp = [0] * (n + 1)

for i in range(n):
    current_char = s[i]
    prev_prev = 0
    for j in range(1, n + 1):
        current = dp[j]
        if current_char == t[j - 1]:
            dp[j] = prev_prev + 1
        else:
            if dp[j - 1] > dp[j]:
                dp[j] = dp[j - 1]
        prev_prev = current

print(n - dp[n])

01159: Palindrome ​

01159: Palindrome