תת־הסדרה המשותפת הארוכה ביותר
שיעור 6 מתוך 15 בקורס תכנות דינמי 101 של Coddy.
תת-הסדרה המשותפת הארוכה ביותר (LCS) היא בעיה קלאסית במדעי המחשב, העוסקת במציאת תת-הסדרה הארוכה ביותר המשותפת לשתי סדרות. תת-סדרה היא סדרה שניתן לגזור מסדרה אחרת על ידי מחיקה של כמה איברים או אף אחד מהם, בלי לשנות את סדר האיברים שנותרו.
לדוגמה, נבחן שתי סדרות:
S1 = "AGGTAB"
S2 = "GXTXAYB"
תת-הסדרה המשותפת הארוכה ביותר של S1 ו-S2 היא "GTAB", ואורכה 4.
יש כמה גישות לפתרון בעיית LCS, והפופולרית ביותר היא גישת התכנות הדינמי.
אתגר
בינוניכתבו פונקציה שמקבלת שתי מחרוזות כקלט ומחזירה את האורך של תת־הרצף המשותף הארוך ביותר שלהן.
הערה: האלגוריתם הזה (יחד עם האלגוריתמים הבאים בקורס הזה) נחשב לאלגוריתם מתקדם, וייתכן שלמתכנתים מתחילים יהיה קשה למצוא בעצמם את פתרון התכנות הדינמי היעיל. אל תהססו להשתמש ברמזים או בלחצן 'Ask AI'!
נסו בעצמכם
def longest_common_subsequence(str1, str2):
# כתבו כאן קודכל השיעורים ביחידה תכנות דינמי 101
תרגלו בעצמכם: קומפיילר Python אונליין