Saya perlu menemukan algoritma pemrograman dinamis untuk menyelesaikan masalah ini. Saya mencoba tetapi tidak dapat menemukannya. Inilah masalahnya:
Anda diberikan serangkaian n karakter s[1...n], yang Anda yakini sebagai dokumen teks rusak yang semua tanda bacanya telah hilang (sehingga terlihat seperti "itwasthebestoftimes..."). Anda ingin merekonstruksi dokumen menggunakan kamus, yang tersedia dalam bentuk fungsi Boolean dict(*) sehingga, untuk setiap string w, dict(w) memiliki nilai 1 jika w adalah kata yang valid, dan memiliki nilai 0 jika tidak.
- Berikan algoritma pemrograman dinamis yang menentukan apakah string s[*] dapat disusun kembali sebagai rangkaian kata yang valid. Waktu berjalan paling banyak harus O(n^2), dengan asumsi bahwa setiap panggilan ke dict membutuhkan waktu satuan.
- Jika string tersebut valid, buat algoritme Anda mengeluarkan urutan kata yang sesuai.