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

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

如果您的字符串以问号开头和结尾，则第一个字符（0 或 1）有 2 种可能性，在这两种情况下运行贪心算法并取最佳值。

Likao指出的错误答案：

贪婪有效，但您必须从紧接在已知数字后面的第一个问号开始。

Answer 2

它简单的回溯imo。为什么用贪婪或动态来复杂化它。