Subsekuens bersama terpanjang
Pelajaran 6 dari 15 dalam kursus Dasar-Dasar Pemrograman Dinamis di Coddy.
Longest Common Subsequence (LCS) adalah masalah klasik dalam ilmu komputer yang melibatkan pencarian subsekuens terpanjang yang sama pada dua sequence. Subsekuens adalah sequence yang dapat diperoleh dari sequence lain dengan menghapus beberapa atau tidak ada elemen tanpa mengubah urutan elemen yang tersisa.
Sebagai contoh, perhatikan dua sequence:
S1 = "AGGTAB"
S2 = "GXTXAYB"
LCS dari S1 dan S2 adalah "GTAB" dengan panjang 4.
Ada beberapa pendekatan untuk menyelesaikan masalah LCS, dan pendekatan yang paling populer adalah pemrograman dinamis.
Tantangan
SedangTulis sebuah fungsi yang menerima dua string sebagai input dan mengembalikan panjang subsekuens umum terpanjangnya.
Catatan: Ini, bersama dengan algoritma yang akan dibahas berikutnya dalam kursus ini, dianggap sebagai algoritma tingkat lanjut dan mungkin sulit bagi programmer baru untuk menemukan solusi DP yang efisien sendiri. Jangan ragu untuk menggunakan petunjuk atau tombol 'Ask AI'!
Coba sendiri
def longest_common_subsequence(str1, str2):
# Tulis kodemu di siniSemua pelajaran di Dasar-Dasar Pemrograman Dinamis
3Algoritma pemrograman dinamis
Subsekuens bersama terpanjangMasalah knapsackMasalah penukaran koinJarak editLatihan sendiri: Compiler Python online