algorithm - 动态规划方法或贪婪失败的案例

Question

我有一个长度为 1 <= |S| <= 100 的字符串和 K (1 <= K <= 10)

这个字符串包含digits < K和问号。我想用 digits < K 替换这些问号，没有两个相邻的数字是相等的。该字符串是圆形的，所以它不能像这样:1?1或 11? .

结果字符串必须是字典序中最小的。

示例输入和输出

input:
K = 4
string = ?????

output:
01012

我尝试了一种贪婪的方法，但它对一些未知的测试用例失败了。我认为它需要一个 dp 方法但无法弄清楚状态，并且纯递归代码不适合时间。

对 dp 方法有什么帮助，或者贪心失败的棘手测试用例？

谢谢，

Answer 1

如果你在字符串的一端有一个数字，贪心算法会给你正确的答案。

如果您的字符串以问号开头和结尾，那么第一个字符有 2 种可能(0 或 1)，对这两种情况都运行贪心算法并取最好的。

Likao 指出的错误答案:

贪心法有效，但您必须从紧跟在已知数字之后的第一个问号开始。