Самая длинная общая подпоследовательность

Опишу-ка я некоторые алгоритмы которые "я всегда знал но забыл".
Начнем с длины самой длинной общей подпоследовательности.
Пусть у нас есть два массива A=(a1...ai) и B=(b1...bj)
Тогда LCS(A,B)=:
1. 0 если i==0 или j==0;
2. LCS((a1...ai-1) ,(b1...bj-1))+1, если ai==bj
3. MAX(LCS((a1...ai-1) ,(b1...bj)),LCS((a1...ai) ,(b1...bj-1))), если ai!=bj

Это достаточно очевидные утверждения, и по ним уже можно составить алгоритм.
Алгоритм просто напрашивается:

int lcs(int* a,int N1,int* b,int N2)

{

    if(N1==0 && N2==0)

        return 0;

    if(a[N1-1) == b[N2-1])

        return 1+lcs(a,N1-1,b,N2-1);

    return max(lcs(a,N1,b,N2-1),lcs(a,N1-1,b,N2))

}

красотища...если бы не одно но. очень медленно.
И в целом почти сразу понятно почему. Мы не храним промежуточные вычисления а каждый раз делаем их заново.
Класический пример такой проблемы - вычесление чилес Фибоначчи по рекурсии:

int F(int N)

{

    return (N<2)?1:F(N-2)+F(N-1);

}

Улучшить это можно, сохраняя промежуточные результаты вычислений. Этот прием называется "меморизация". Т.е. вообще-то он называется "Memoization", но надо же как-то по русски сказать.

В данном случае для меморизации нам понадобится массив размером [i*j].
Но тут возникает интересный вопрос - а зачем нам тогда рекурсия здалась?
И возникает примерно такой код (пробывать не советую, не тестировал, могу ошибиться с индексами)

int lcs_array(int* a,int N1,int* b,int N2)

{

    int* c = new int[N1*N2];

    memset(c,0,N1*N2*sizeof(int));

    for(int i=0;i<N1;++i)

        for(int j=0;j<N2;++j)

            c[i*N2+j]=(a[i]==b[j])?c[(i-1)*N2+j-1]+1:max(c[i*N2+j-1],c[(i-1)*N2+j]);

    int res = c[N1*N2-1];

    delete[] c;

    return res;

}