פּלאַן אַן אַלגערידאַם פֿאַר דערגייונג די לאָנגעסט פּראָסט סאַבסיקוואַנס צווישן צוויי סטרינגס
די לאָנגעסט פּראָסט סאַבסיקוואַנס (LCS) פּראָבלעם איז די פּראָבלעם פון געפֿינען די לאָנגעסט סאַבסיקוואַנס פּראָסט צו צוויי סיקוואַנסיז. עס איז אַנדערש פון די לאָנגעסט פּראָסט סובסטרינג פּראָבלעם: ניט ענלעך סובסטרינגס, סאַבסיקוואַנסיז זענען נישט פארלאנגט צו פאַרנעמען קאָנסעקוטיווע שטעלעס אין דער אָריגינעל סיקוואַנסיז. א קלאַסיש וועג פון סאַלווינג דעם פּראָבלעם איז דורך די נוצן פון דינאַמיש פּראָגראַממינג. דאָ איז אַן אַלגערידאַם וואָס געפינט די לענג פון די לאָנגעסט פּראָסט סאַבסאַקוואַנס צווישן די סטרינגס s1 און s2: 1. יניטיאַליזירן אַ 2D מענגע `dp` מיט דימענשאַנז `(len(s1)+1) X (len(s2)+1)`. דער ערשטער רודערן און זייַל פון דפּ זענען אָנגעפילט מיט זעראָס צו פאָרשטעלן די באַזע פאַל ווו די לענג פון איינער פון די סטרינגס איז נול. 2. אָנהייב יטערייטינג דורך די אותיות פון S1 און S2. זאל 'i' און 'j' זיין די ינדיסיז פון די אותיות אין s1 און s2, ריספּעקטיוולי. 3. פֿאַר יעדער פּאָר פון אותיות, אויב `s1[i] == s2[j]`, דעמאָלט די לענג פון די פּראָסט סאַבסאַקוואַנס וואָס ענדיקט זיך מיט אינדעקס `i` אין ס1 און `j` אין ס2 איז איינער מער ווי די לענג פון דער פּראָסט סאַבסאַקוואַנס סאָף אין די פריערדיקע אינדעקס אין ביידע סטרינגס. אין אנדערע ווערטער, `dp[i+1][j+1] = dp[i][j] +1`. 4. אָבער, אויב די אותיות זענען נישט גלייַך, די לענג פון די LCS וואָלט זיין די מאַקסימום פון די LCS וואָס ענדיקט זיך אין די פריערדיקע אינדעקס אין s1 אָדער די LCS וואָס ענדיקט זיך מיט די פריערדיקע אינדעקס אין s2. אזוי, `dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])`. 5. צוריקקומען די ווערט אין די לעצטע צעל פון די דפּ טיש, הייסט `dp[-1][-1]`. צו געפֿינען די פאַקטיש לאָנגעסט פּראָסט סאַבסיקוואַנס, מיר קענען צוריקקריגן דורך די דפּ טיש סטאַרטינג פון די לעצטע צעל: 1. יניטיאַליזע אַ ליידיק שטריקל `לקס`. 2. אָנהייב פֿון די לעצטע צעל `dp[-1][-1]` און מאַך צו דער ערשטער צעל `dp[0][0]`. 3. אויב די אותיות אין די קראַנט צעל ס ינדיסעס אין s1 און s2 זענען גלייַך, דער כאַראַקטער איז טייל פון די LCS. לייג עס צו די 'לקס' שטריקל און מאַך דייאַגאַנאַלי צו די שפּיץ-לינקס צעל. 4. אַנדערש, מאַך צו די צעל מיט די גרעסערע ווערט, אָדער אויבן די קראַנט צעל אָדער צו זיין לינקס. 5