在 C++ 中使用追加和克隆操作进行字符串构造的最优成本计算

问：

问题概述：

我正在研究一个字符串构造挑战，我的目标是从头开始构建一个目标字符串。该过程涉及两个主要操作：

1. 将任何字符追加到当前字符串。此操作具有固定成本，表示为 （x）。
2. 从当前字符串克隆特定子字符串并将其追加到末尾。此操作有其自己的固定成本，表示为 （y）。

主要目标是确定构造整个目标字符串的最具成本效益的方法，同时考虑这两种操作的成本。

对于给定的字符串，将同时提供追加成本 （（x）） 和克隆成本 （（y））。挑战在于计算使用两种操作的组合构造字符串所需的最小可能成本。

我首先实施了一种动态编程方法来解决这个问题。我的策略是遍历字符串，并在每个位置决定是附加字符还是克隆子字符串更划算。

我尝试了什么：
对于字符串中的每个位置，我计算了附加下一个字符的成本。然后，我检查了是否有可以克隆的先前子字符串以匹配目标字符串的一部分。如果克隆操作比附加操作更具成本效益，我选择了克隆。我维护了一个表格，以跟踪构建每个位置的字符串所需的最低成本。

期望：
考虑到追加和克隆的约束和成本，我希望我的解决方案能够正确计算构造各种目标字符串的最小成本。

实际结果：
但是，对于某些输入字符串，计算的成本与预期结果不同。具体来说，当手动逐步分解某些字符串时，产生的最佳成本与我的解决方案生成的成本不同。

例如，对于附加成本为 10 且克隆成本为 1 的字符串“abababab”，我的初始逻辑将成本计算为 22，而手动细分建议成本应为 21。