Теорема 1.

Пусть Z = z₁, z₂, . . . z_k - одна из наибольших общих подпоследовательностей для X = x₁, x₂, . . . x_m и Y = y₁, y₂, . . . y_n . Тогда:

1) если x_m = y_n, то z_k =x_m = y_n и Z_k-1является НОП для X_m-1 и Y_n-1;

2)если x_m ≠ y_n, и z_k ≠ x_m , то Z является НОП для X_m-1 и Y.

3)если x_m ≠ y_n и z_k ≠ y_n , то Z является НОП для X_m и Y_n-1.

 

НОП двух последовательностей содержит в себе наибольшую общую подпоследовательностей их префиксов. Таким образом задача о НОП обладает свойством оптимальности для подзадач.