מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/תת מחרוזת ארוכה ביותר - דוגמת הרצה/תשובה

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה אל: ניווט, חיפוש

ראשית נצייר את עץ הקריאות לLCS-Length:



כל צומת מתאר את הארגומנטים שאתם נקראת הפונקציה, והמחרוזות מימין לכל צומת מתארות את תתי-המחרוזות המושוות. כך, לדוגמה, הראש מתאר את זאת שבתחילה נקראת LCS-Length(3, 2), כלומר על המחרוזות עיבוד הנוסחה נכשל (שגיאת תחביר): {\displaystyle \displaystyle "cab"} ועיבוד הנוסחה נכשל (שגיאת תחביר): {\displaystyle \displaystyle "ca"} .

כל קשת מתארת את הערך המוחזר כלפי מעלה. אם יש שני ערכים מוחזרים כלפי מעלה לצומת מילדיו, הצומת מעביר מעלה את הגדול מביניהם.

התרשים הבא מראה את מצבן הסופי של שתי המטריצות: