是的,有一个动态程序可以直接从下面实现的Python算法中提取出来,该算法用于验证解决方案。
def has_good_form(s):
previous_letter = None
needs_adjacent_copy = False
for letter in s:
if letter == previous_letter:
needs_adjacent_copy = False
elif not needs_adjacent_copy:
previous_letter = letter
needs_adjacent_copy = True
else:
return False
return not needs_adjacent_copy
print(has_good_form("aca"))
print(has_good_form("aaa"))
print(has_good_form("abcdef"))
print(has_good_form("aaddff"))
has_good_form()
函数会记住先前的字母以及是否已知有相邻的副本,总共有26×2=54个状态,再加上初始状态(共55个)。动态规划的思想是,对于每个状态和时间,最便宜的修改集合是什么,可以将has_good_form()
函数置于该状态在该时间?具体实现如下(未经测试)。
import collections
import math
import string
def distance(a, b):
return abs(ord(a) - ord(b))
def cheapest_good_form(s):
state_to_min_cost = {(None, False): 0}
for original_letter in s:
options = collections.defaultdict(list)
for state, min_cost in state_to_min_cost.items():
previous_letter, needs_adjacent_copy = state
for letter in string.ascii_lowercase:
cost = min_cost + distance(original_letter, letter)
if letter == previous_letter:
options[(letter, False)].append(cost)
elif not needs_adjacent_copy:
options[(letter, True)].append(cost)
state_to_min_cost = {state: min(costs) for (state, costs) in options.items()}
return min(
(
cost
for (
(_, needs_adjacent_copy),
cost,
) in state_to_min_cost.items()
if not needs_adjacent_copy
),
default=math.inf,
)
print(cheapest_good_form(""))
print(cheapest_good_form("a"))
print(cheapest_good_form("aca"))
print(cheapest_good_form("abcdef"))