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