爲正拼圖問題

Question

DP的做法是那裏的n-puzzle問題DP方法

感謝所有，認識到...

拉詹

Answer 1

動態規劃是用來解決問題的技術通過遞歸方式將疑難病例簡化爲簡單病例，直至找到足夠簡單的病例來解決「通過檢查」。因此，如果在每個階段可以考慮採取一種降低問題複雜性的舉措，那麼對於n-puzzle問題只能有一個合理的DP方法。例如，如果一個n-puzzle中的第一個「移動」總是使它變成一個「（n-1）-puzzle」（對於「移動」的某個具體定義，並且假設（n-1） -puzzle有意義），那麼你可以應用DP，最終解決「1--難題」，並向上組成向上解決n-puzzle。

我不知道任何這樣的n拼圖簡化過程;現在我想不起來。但是，這並不意味着不存在。