动态规划求解最短回文字符串构造成本-Python教程-PHP中文网

动态规划求解最短回文字符串构造成本

本文讲解如何使用动态规划解决“最小成本构造指定长度回文字符串”问题：给定合法相邻字符对（rune pairs）及其代价，求构造长度恰好为 k 的回文字符串的最小总代价；若不可行则返回 -1。

本文讲解如何使用动态规划解决“最小成本构造指定长度回文字符串”问题：给定合法相邻字符对（rune pairs）及其代价，求构造长度恰好为 k 的回文字符串的最小总代价；若不可行则返回 -1。

该问题本质是带约束的最优化回文构造问题，核心在于：

字符串必须是回文（正读反读一致）；
所有相邻字符对（即长度为 2 的子串）必须在输入中显式给出，且代价已知；
总代价 = 字符串中所有连续二元组（s[0:2], s[1:2], ..., s[k−2:k]）的代价之和；
目标：在满足长度 k 和回文约束下，最小化总代价。

⚠️ 关键理解澄清（针对原文困惑）：

字符串长度 k 指字符数（如 "abba" 长度为 4），而非 rune pair 数量；
一个长度为 k 的字符串包含 k−1 个重叠的相邻字符对（即 s[i:i+2]，i 从 0 到 k−2）；
例如 "abbaacaabba"（长度 11）含 10 个 rune pairs：ab, bb, ba, aa, ac, ca, aa, ab, bb, ba —— 但题干样例误写为 abbaacaabba. 并只列出 6 个，实为笔误；正确解析应为全部 10 个重叠对。
回文约束意味着：若字符串为 s[0..k−1]，则对所有 i ∈ [0, k−1]，有 s[i] == s[k−1−i]。

因此，构造过程不能暴力枚举所有回文（26ᵏ 量级），而应利用回文对称性 + 动态规划：

✅ 正确解法思路（DP 状态设计）

由于回文由中心向两侧扩展，且代价仅依赖相邻字符，我们按「回文半径」或「区间长度」设计状态更自然：

定义 dp[l][r][a][b] 表示：构造回文子串 s[l..r]（闭区间），其中 s[l] = a、s[r] = b 时的最小代价。
但 k ≤ 100，四维状态空间过大（100×100×26×26 ≈ 6.7M），可优化。

更高效方式：按回文长度从小到大 DP，只记录两端字符

设 dp[len][a][b] = 构造长度为 len 的回文字符串，且首尾字符分别为 a 和 b 的最小代价（注意：因回文，必有 a == b 当 len 为奇数且 a,b 是最外层；但更通用做法是固定 s[0]=a, s[len−1]=b，由回文约束得 a==b）。

绘蛙AI视频

绘蛙AI视频是一款面向电商营销的图片转视频和模特动态视频生成工具。

下载

✅ 实际推荐状态：
dp[i][j] = 构造长度为 i 的回文，且最外层字符对为 j（即 s[0]s[i−1]）的最小代价。
但需支持内部递归填充。

更标准且简洁的做法是：
令 dp[l][r] 表示回文区间 [l, r] 的最小构造代价，其中 s[l] 和 s[r] 已确定（由转移决定）。
但输入未给出单字符代价，只给二元组代价 → 所有代价均来自相邻对，因此：

长度为 1 的字符串：无相邻对 → 代价为 0（但题目要求 k ≥ 2，故无需考虑）；
长度为 2 的回文：形如 "aa", "bb"…，代价 = cost["aa"]（若存在）；
长度为 3 的回文：形如 "aba"，含对 "ab" 和 "ba" → 代价 = cost["ab"] + cost["ba"]；
长度为 4 的回文："abba" → 对 "ab", "bb", "ba" → 代价 = cost["ab"] + cost["bb"] + cost["ba"]。

观察发现：任意回文 s 的代价 = 所有 s[i:i+2]（i=0..k−2）代价之和。
而回文结构意味着：
s[0:k] 是回文 ⇔ s[i] = s[k−1−i]，因此 s[i:i+2] 与 s[k−2−i:k−i] 存在镜像关系，但代价仍需独立累加（因每对位置不同）。

✅ 最优子结构：
要构造长度为 k 的回文 s，可考虑其最外层两个字符 x 和 y（必有 x == y），则：

若 k == 2：s = "xx"，代价 = cost["xx"]（若存在）；
若 k == 3：s = "xyx"，代价 = cost["xy"] + cost["yx"]；
若 k ≥ 4：s = "x" + t + "x"，其中 t 是长度为 k−2 的回文，且 t 的首字符必须与 "x" 拼接成合法对 "xt[0]"，末字符同理（因 s[1] = t[0], s[k−2] = t[k−3]，且 s[0:2]="xt[0]", s[k−2:k]="t[k−3]x"）。

因此，定义：
dp[length][first][last] = 构造长度为 length 的回文，首字符为 first、尾字符为 last 的最小代价（由回文性质，first 必须等于 last，故可简化为 dp[len][c] 表示首尾均为字符 c 的最小代价）。

但中间部分 t 的首尾也受约束：t 本身是回文，且 s[0:2] = "c" + t[0] 必须存在代价，s[len−2:len] = t[-1] + "c" 也必须存在代价。

故状态应为：
dp[l][a][b] = 构造长度为 l 的回文，且 s[0] = a, s[l−1] = b 的最小代价。
由回文 ⇒ a == b，所以实际只需 dp[l][a]，但转移时需知道 s[1] 和 s[l−2]（即 t 的首尾）以查 cost["a"+s[1]] 和 cost[s[l−2]+"a"]。

最终推荐实现（Python 伪代码）：

from collections import defaultdict
import sys

# 输入解析
n, k = map(int, input().split())
cost = {}
for _ in range(n):
    line = input().split()
    pair, c = line[0], int(line[1])
    cost[pair] = c

# dp[l][a][b] = min cost to build palindrome of length l with s[0]==a, s[l-1]==b
# Since palindrome => a must equal b, we use dp[l][a] but store transitions via inner chars
# Instead, use dp[l][i][j]: i,j are 0..25 (a->0, z->25), meaning s[0]=chr(i+'a'), s[l-1]=chr(j+'a')
# Initialize with inf
INF = float('inf')
dp = [[[INF] * 26 for _ in range(26)] for _ in range(k + 1)]

# Base case: length 2
for a in range(26):
    for b in range(26):
        pair = chr(a + ord('a')) + chr(b + ord('a'))
        if pair in cost:
            if a == b:  # "aa" is palindrome
                dp[2][a][b] = cost[pair]

# Base case: length 3 -> "aba": need "ab" and "ba"
for a in range(26):
    for b in range(26):
        ab = chr(a + ord('a')) + chr(b + ord('a'))
        ba = chr(b + ord('a')) + chr(a + ord('a'))
        if ab in cost and ba in cost:
            dp[3][a][a] = cost[ab] + cost[ba]  # s[0]=a, s[2]=a, s[1]=b

# Fill for length l from 4 to k
for l in range(4, k + 1):
    for a in range(26):  # s[0] and s[l-1] must both be a
        for mid_first in range(26):   # s[1]
            for mid_last in range(26): # s[l-2], must equal mid_first for palindrome? No: s[l-2] must equal s[1] only if l=4; generally s[1] == s[l-2] by palindrome
            # Actually: for palindrome s[0..l-1], s[1] == s[l-2], s[2] == s[l-3], etc.
            # So inner substring s[1:l-1] is itself a palindrome of length l-2, with s[1] == s[l-2]
            # Thus: dp[l][a][a] = min over b of { cost["ab"] + dp[l-2][b][b] + cost["ba"] }
            # where "ab" = s[0:2], "ba" = s[l-2:l]
            b = mid_first
            ab = chr(a + ord('a')) + chr(b + ord('a'))
            ba = chr(b + ord('a')) + chr(a + ord('a'))
            if ab in cost and ba in cost and dp[l-2][b][b] != INF:
                new_cost = cost[ab] + dp[l-2][b][b] + cost[ba]
                if new_cost <p>? 注意事项：  </p>