動態規劃方法或失敗的貪婪

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），請在兩種情況下運行貪婪算法並採取最佳措施。由Likao指出

錯誤答案：

貪婪的作品，但你必須與第一個問號剛剛已知數字之後是開始。

Answer 2

它簡單的回溯imo.Why使它與貪婪或動態複雜化。