Динамичко програмирање

Увод

Динамичко програмирање је моћна техника за конструкцију алгоритама која се користи за решавање различитих група проблема. Као и подели па владај и динамичко програмирање је подскуп индуктивно-рекурзивне технике за конструкцију алгоритама. Полазни проблем делимо на подпроблеме, рекурзивно их решавамо и затим решења подпроблема обједињујемо у решење полазног проблема.

Да бисмо могли да применимо динамичко програмирање, полазни проблем мора да испуњава два услова:

1. Преклапање подпроблема - Приликом поделе полазног проблема на подпроблема, исти подпроблеми се појављују више пута. Прецизније, решење једног подпроблема зависи од решења других подпроблема или има утицај на њих.
2. Оптимална подструктура - Оптимално решење проблема сачињено је од оптималних решења његових подпроблема на сваком нивоу.

Кључно својство динамичког програмирања као технике за конструкцију алгоритама јесте избегавање вишеструког решавања идентичних подпроблема. Уместо тога, сваки подпроблем решавамо тачно једном и памтимо његово решење. Када током решавања полазног проблема или његових подпроблема поново наиђемо на већ решени подпроблем, нећемо га решавати изнова, већ ћемо искористити од раније познато решење. Дакле. кључна идеја динамичког програмирања је паметно трошење меморије да бисмо уштедели време. У пракси, динамичким програмирањем се експоненцијална решења најчешће спуштају на полиномијална.

На крају, потребно је нагласити разлике између подели-па-владај и динамичког програмирања:

• Подели па владај користимо када проблем можемо да поделимо на независне подпроблеме, тј. решавање једног подпроблема не зависи од, нити утиче на, решења других подпроблема. Подели па владај се ослања на принцип смањи за фактор, чиме се наивни кваратни алгоритми своде на логлинеарне. У случају да постоји преклапање подпроблема, подели па владај се не сме користити. Такође, подели па владај води ка неефикасним алгоритмима ако је подела на подпроблеме тривијална, тј. ако се своди на смањи за један. Кључна идеја је независно решавање подпроблема и комбиновање њихових решења у решење полазног проблема.
• Динамичко програмирање користимо када проблем можемо да поделимо на подпроблеме који се преклапају, тј. када решење једног подпроблема зависи од решења других подпроблема и када проблем испуњава својство оптималне подструктуре. За разлику од подели па владај, примена динамичког програмирања зависи само од проблема који се решава и не зависи од начина на који се проблем дели на подпроблема. Кључна идеја је избегавање вишеструког решавања идентичних подпроблема, тако што ћемо решења једном решених подпроблема сачувати и касније их само користити када год наиђемо на већ решени подпроблем.

Динамичким програмирањем се могу решити две класе проблема:

1. Проблеми пребројавања - Најчешће се ради о проблемима у којима је потребно пребројати на колико начина се неки задатак може решити. На пример, одредити број комбинација, број растављања броја на збирове, на колико начина се може вратити кусур итд.
2. Оптимизациони проблеми - Потребно је одредити максимално или минимално решење које испуњава дати скуп ограничења. На пример, одређивање максималне вредности предмета који се могу спаковати у ранац, одређивање минималног броја трансформација потребних да се једна реч пребаци у другу итд.

Треба приметити да се динамичко програмирање у свом основном облику фокусира само на добијање нумеричког решење, али не и на то како се до решења долази. Реконструкција решења је посебан проблем који даје одговор на питање како се до траженог нумеричког решења долази. У пракси се током извршавања алгоритма најчешће памте неке додатне информације које ће тек након целокупног решавања проблема, тј. одређивања нумеричког решења, бити коришћене за реконструкцију и одређивања начина на који се то нумеричко решење постиже.

Развијање алгоритма динамичким програмирањем има 4 фазе:

1. Индуктивно-рекурзивна конструкција решења - Решење проблема је потребно описати рекурентном релацијом. Приликом дефинисања рекурентне релације користимо све оне праксе дефинисане у опису индуктивно-рекурзивне технике за конструкцију алгоритама. Најчешће, директна имплементација рекурзивног алгоритма који прати индуктивно-рекурзивну конструкцију води ка решењу експоненцијалне временске сложености, што је неприхватљиво у пракси.
2. Мемоизација - Потребно је увести помоћну структуру података у којој ћемо памтити решења подпроблема. Други назив за овај корак је динамичко програмирање на ниже, јер током решавања крећемо од проблема величине $n$ и низом рекурзивних позива га постепено сводимо на базни случај. Чим решимо подпроблем, његово решење памтимо у помоћној структури података. Сваки следећи пут када наиђемо на тај исти подпроблем, само ћемо то познато решење прочитати, без поновног решавања. Оваквим поступком се алгоритам експоненцијалне сложености из корака 1 преводи у алгоритам полиномијалне сложености. Мемоизација је рекурзивни поступак и као основну ману има додатну меморијску сложеност због великог броја рекурзивних позива.
3. Елиминација рекурзије - Проблем можемо да решимо и итеративно. Потребно је да кренемо од основног случаја и систематски да изградимо решење читавог проблема. Решавање проблема се своди на попуњавање помоћне структуре података од мањих ка већим подпроблемима. Други назив за решавање проблема на овај начин је динамичко програмирање на више.
4. Меморијска оптимизација - Приликом решавања проблема одоздо на горе, тј. динамичким програмирањем на више, често нам за решавање текућег подпроблема нису потребна решења свих мањих подпроблема већ само неколико њих. У том случају, сва непотребна решења можемо да одбацимо и да их не чувамо. Тиме се може постићи незанемарљива уштеда у потрошњи меморије.
5. Реконструкција решења - Реконструкција решења није основни део алгоритма добијеним динамичким програмирањем. Да бисмо реконструисали решење, често је потребно да током попуњавања структуре података у кораку 3 чувамо додатне информације којима ћемо кодирати на који начин смо до тог решења дошли. У пракси се најчешће одлучујемо или за меморијску оптимизацију или за реконструкцију решења, јер није могуће постићи обе ствари истовремено.

Свему овоме претходи провера да ли проблем који се решава поседује оптималну подструктуру и да ли се подпроблеми преклапају. Ако проблем не испуњава ова два услова, динамичко програмирање се не може применити.

Напомена: У свим решењима бавићемо се искључиво алгоритмима, док учитавање и штампање резултата препуштамо читаоцу за вежбу.

Задатак 1

Корисник уноси природан број $n$. Написати програм који одређује $n$-ти Фибоначијев број. Фибоначијеве бројеве можемо израчунати уз помоћ следеће рекурентне релације:

$$\begin{aligned} F(n) = \begin{cases} 1, \quad & \text{за} x \le 1 \\ F(n - 1) + F(n-2), \quad & \text{за} x > 1 \end{cases} \end{aligned}$$

Улаз: У јединој линији стандардног улаза уноси се природан број $n$ ($1 \le n \le 50$).

Излаз: У јединој линији стандардног излаза исписати $n$-ти Фибоначијев број.

Решење

Задатак можемо директно решити имплементирањем рекурзивне функције која прати наведену рекурентну релацију. Имплементација је у наставку:

static int fib(int n)
{
    // базни случај
    if (n == 0 || n == 1)
        return 1;
    // решење одређујемо према рекурентној формули
    return fib(n-1) + fib(n-2);
}

Иако синтаксно кратко, приказано решење је експоненцијалне временске сложености. Узрок томе је преклапање подпроблема које се може врло лако уочити. На пример, размотримо израчунавање $F(4)$:

Са приказаног стабла израчунавања лако се уочава преклапање подпроблема, јер се у левом и десном подстаблу налазе идентична стабла. Са сваким следећим фибоначијевим бројем, преклапање подпроблема се погоршава, па је јасно зашто желимо да избегнемо вишеструко израчунавање истих подпроблема. Да бисмо то учинили, потребно је да уведемо помоћну структуру података у којој ћемо чувати већ решене подпроблеме.

Као помоћну структуру података користићемо низ. Индекс низа ће бити редни број фибоначијевог броја, а вредност низа ће бити фибоначијев број. С обзиром да користимо помоћну структуру, потребно је да осмислимо како ћемо разликовати решене од нерешених проблема. Фибоначијеви бројеви су већи од нула, па ће вредност нула у низу означавати да проблем није решен. Ако је вредност различита од нула, то значи да је проблем већ решен и да га не морамо поново решавати. Мемоизовано решење је у наставку:

static int fib(int n, int[] memo)
{
    // ако је проблем већ решен, само враћамо решење
    if (memo[n] != 0)
        return memo[n];
    // ако није, прво уписујемо решење, па враћамо резултат
    if (n == 0 || n == 1)
        return memo[n] = 1;
    // рекурзивно решавамо подпроблем и чувамо његове решење за касније
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    // враћамо резултат
    return memo[n];
}
static int fib(int n)
{
    // креирамо помоћну структуру података у којој чувамо
    // решења подпроблема
    int[] memo = new int[n+1];
    // рекурзивно решавамо проблем динамичким програмирањем на ниже
    return return fib(n, memo);
}

Следећи корак у конструкцији алгоритма је елиминација рекурзије. Да бисмо рекурзију елиминисали потребно је да проблем решавамо одоздо на горе, тј. динамичким програмирањем на више. Да бисмо то постигли, треба да кренемо од базног случаја и да систематски решавамо веће проблеме знајући решења мањих. Решење динамичким програмирањем на више је у наставку:

static int fib(int n) 
{
    // креирамо помоћну структуру података
    int[] memo = new int[n];
    // попуњавамо решења основних случајева
    memo[0] = 1;
    if (n == 0)
        return memo[0];
    memo[1] = 1;
    if (n == 1)
        return memo[1];
    // итеративно решавамо проблем комбинујући решења
    // мањих подпроблема у решења већих
    for (int i = 2; i <= n; i++)
        memo[i] = memo[i-1] + memo[i-2];
    // враћамо решење целог проблема
    return memo[n];
}

Из итеративног решења треба приметити да оно представља примену рекурентне релације у “супротном смеру”, тј. са десна на лево. Ова правилност се често јавља у кораку елиминације рекурзије и представља брз трик у конструкцији решења.

На крају остаје нам да покушамо да извршимо меморијску оптимизацију. Да бисмо то урадили, довољно је да уочимо да наше решење директно зависи само од решења два директна претходника. Меморијски оптимизовано решење је у наставку:

static int fib(int n) 
{
    // креирамо помоћне променљиве
    int tekuci, prethodni;
    // попуњавамо решења основних случајева
    prethodni = 1;
    if (n == 0)
        return prethodni;
    tekuci = 1;
    if (n == 1)
        return tekuci;
    // итеративно решавамо проблем комбинујући решења
    // мањих подпроблема у решења већих
    for (int i = 2; i <= n; i++)
    {
        int memo = tekuci + prethodni;
        prethodni = tekuci;
        tekuci = memo;
    }
    // враћамо решење целог проблема
    return tekuci;
}

Меморијска оптимизација у овом случају је врло једноставна, међутим то најчешће није случај. У многим проблемима меморијска оптимизација захтева пажљиво анализирање редоследа решавања подпроблема, а у многим случајевима није могућа. Приказано меморијски оптимизовано решење је линеарне временске сложености и константне просторне сложености.

Задатак 2

Написати програм који одређује број комбинација без понављања дужине $k$ из скупа од $n$ елемената.

Улаз: Са стандардног улаза се учитава број $k$ ($0 \le k \le n$) и број $n$ ($1 \le n \le 40$).

Излаз: На стандардни излаз исписати тражени број комбинација.

Решење

Задатак можемо да решимо директном применом формуле за израчунавање броја комбинација:

$$\binom{n}{k} = \frac{n!}{(n-k)!(k)!}$$

Имплементација је у наставку:

static int faktorijel(int n)
{
    int f = 1;
    for (int i = 1; i <= n; i++)
        f = f*i;
    return f;
}
static int broj_kombinacija(int n, int k) 
{
    return faktorijel(n)/(faktorijel(n-k)*faktorijel(k));
}

Иако једноставно за имплементацију, приказано решење није употребљиво. Наиме, због ограничења величине типова, ова формула се не може употребити за параметре који су већи од 20. У пракси, често желимо да радимо са већим бројевима. Да бисмо то постигли, можемо да се присетимо Паскаловог троугла:

$$\begin{aligned} & 1 & & & & & \\ & 1 & 1 & & & & \\ & 1 & 2 & 1 & & & \\ & 1 & 3 & 3 & 1 & & \\ & 1 & 4 & 6 & 4 & 1 & \\ & \ldots \end{aligned}$$

Троугао можемо записати и експлицитним формулама:

$$\begin{aligned} & \binom{0}{0} & & & & & \\ & \binom{1}{0} & \binom{1}{1} & & & & \\ & \binom{2}{0} & \binom{2}{1} & \binom{2}{2} & & & \\ & \binom{3}{0} & \binom{3}{1} & \binom{3}{2} & \binom{3}{3} & & \\ & \binom{4}{0} & \binom{4}{1} & \binom{4}{2} & \binom{4}{3} & \binom{4}{4} & \\ & \ldots & & & & & \end{aligned}$$

Користећи Паскалов троугао, можемо лако да уочимо и Паскалов идентитет:

$$\begin{aligned} \binom{n}{k} = \begin{cases} 1, & \quad \text{ за } k = 0 \lor k = n \\ \binom{n-1}{k-1} + \binom{n-1}{k}, & \quad \text{ за } 1 < k < n \end{cases} \end{aligned}$$

Имплементација директно прати рекурентну релацију:

static int broj_kombinacija(int n, int k)
{
    // основни случај
    if (k == 0 || k == n)
        return 1;
    // рекурзивно решавамо подпроблеме и конструишемо решење
    return broj_kombinacija(n-1, k-1) + broj_kombinacija(n-1, k);
}

Приказано решење је експоненцијалне временске сложености. Решење можемо да убрзамо применом мемоизације. С обзиром да наш проблем зависи од два параметра $n$ и $k$, као помоћну структуру података можемо да користимо $(n+1) \times (n+1)$ матрицу. С обзиром да је број комбинација природан број, број $0$ у помоћној структури можемо да искористимо као сигнал да подпроблем није раније решаван. Мемоизовано решење је у наставку:

static int broj_kombinacija(int n, int k, int[,] memo)
{   
    // ако смо проблем већ решавали, само враћамо решење
    if (memo[n,k] != 0)
        return memo[n,k];
    // проверавамо базни случај
    if (k == 0 || k == n)
        return memo[n,k] = 1;
    // решавамо проблем и памтимо решење за касније
    memo[n,k] = broj_kombinacija(n-1, k-1, memo) + broj_kombinacija(n-1, k, memo);
    // враћамо решење
    return memo[n,k];
}
static int broj_kombinacija(int n, int k)
{
    // креирамо помоћну структуру података
    int[,] memo = new int[n+1, n+1];
    // проблем решавамо мемоизацијом
    return broj_kombinacija(n, k, memo);
}

Као и у претходном задатку, врло лако можемо елиминисати рекурзију. Довољно је да попуњавамо матрицу, тј. њен доњи троугао, ред по ред. Итеративно решење је у наставку:

static long brojKombinacija(int n, int k)
{
    // креирамо помоћну матрицу
    int[,] memo = new int[n+1, n+1];
    // пролазимо кроз матрицу ред по ред
    for (int i = 0; i <= n; i++)
    {
        // на почетку сваког реда је вредност 1
        memo[i][0] = 1;
        // унутрашња петља рачуна текући елемент према паскаловом идентитету
        for (int ј = 1; ј < n; j++)
            memo[i][j] = memo[j-1][j-1] + memo[i-1][j];
        // на крају сваког реда је вредност 1
        memo[i][i] = 1;
    }
    // враћамо тражени резултат
    return memo[n][k];
}

Итеративно решење се врло лако може меморијски оптимизовати тако да не користимо целу матрицу, већ само доњи троугао. Поред тога, доњи троугао можемо смањити тако да не чува вредности веће од $k$. Меморијска сложеност након ове исправке остаје асимптотски иста, али ће у пракси имати ниже константе факторе.

static long brojKombinacija(int n, int k)
{
    // креирамо степенасту матрицу
    int[][] memo = new int[n+1][];
    for (int i = 0; i <= n; i++)
        memo[i] = new int[Math.Min(k + 1, i + 1)];
    // пролазимо кроз матрицу ред по ред
    for (int i = 0; i <= n; i++)
    {
        // на почетку сваког реда је вредност 1
        memo[i][0] = 1;
        // унутрашња петља рачуна текући елемент према паскаловом идентитету
        for (int ј = 1; ј <= Math.Min(i-1, k); j++)
            memo[i][j] = memo[j-1][j-1] + memo[i-1][j];
        // на крају сваког реда је вредност 1
        if (i <= k)
            memo[i][i] = 1;
    }
    // враћамо тражени резултат
    return memo[n][k];
}

Пажљивијом анализом претходног кода видимо да, како је то обично случај у динамичком програмирању, не морамо истовремено чувати све елементе матрице, јер свака врста зависи само од претходне и довољно је уместо матрице чувати само њене две врсте (претходну и текућу). Заправо, довољно је чувати само један вектор врсту ако је пажљиво попуњавамо и ако током њеног ажурирања у једном њеном делу чувамо текућу, а у другом наредну врсту. Пошто елемент $(n, k)$ зависи од елемента $(n − 1, k − 1)$ и од елемента $(n − 1, k)$ значи да сваки елемент зависи од елемената који су лево од њега, али не од елемената који су десно од њега. Зато ћемо вектор попуњавати здесна налево. Претпоставићемо да током ажурирања важи инваријанта да се на позицијама строго већим од $k$ налазе елементи врсте $n$, а да се на позицијама мањим или једнаким од $k$ налазе елементи врсте $n − 1$. Ажурирање започиње тиме што на крај врсте допишемо вредност $1$ (осим у случају када вршимо сасецање десног дела троугла) и наставља се тако што се елемент на позицији $k$ увећа за вредност на позицији $k − 1$. Заиста, пре ажурирања се на позицији $k$ налази вредност троугла са позиције $(n−1, k)$, док се на позицији $k −1$ налази вредност троугла са позиције $(n−1, k −1)$. Њихов збир је вредност троугла на позицији $(n, k)$, па се он уписује на позицију $k$ и након тога се $k$ смањује за $1$, чиме се инваријанта одржава. Ажурирање се врши до позиције $k = 1$, јер се на позицији $k = 0$ у свим врстама налази вредност $1$.

static long brojKombinacija(int n, int k)
{
    // креирамо помоћни низ
    int[] memo = new int[k+1];
    // иницијализујемо основни случај
    memo[0] = 1;
    // пролазимо кроз матрицу ред по ред
    for (int i = 1; i <= n; i++)
    {
        // дописујемо 1 на крај реда, ако треба
        if (i <= k)
            memo[i][0] = 1;
        // унутрашња петља рачуна текући елемент према паскаловом идентитету
        for (int ј = Math.Min(i-1, k); j > 0; j--)
            memo[j] += memo[j-1];
    }
    // враћамо тражени резултат
    return memo[k];
}

Меморијски оптимизовано решење има квадратну временску сложеност и линеарну просторну сложеност. Динамичким програмирањем смо оригинални експоненцијални алгоритам спустили на полиномијални који се у пракси може користити и за веће вредности параметара $n$ и $k$. Снижавање временске сложености смо постигли чувањем решење подпроблема и систематском изградњом решења полазећи од основног случаја. Да бисмо то постигли свесно смо направили компромис када је меморијска сложеност у питању, тј. намерно трошимо додатну меморију да бисмо уштедели на времену.

Задатак 3

Написати програм који одређује на колико се начина може извући $k$ лоптица из бубња који садржи $n$ различи- тих лоптица, ако се свака извучена лоптица враћа у бубањ пре новог извлачења.

Улаз: Са стандардног улаза се учитава број $k$ ($1 \le k \le n$) и $n$ ($1 \le n \le 30$), сваки из посебног реда.

Излаз: На стандардни излаз исписати тражени број комбинација са понављањем.

Решење

Ако је потребно изабрати $0$ елемената из скупа од $n$ елемената то је могуће урадити само на један начин. Ако је потребно изабрати $k > 0$ елемената из празног скупа, то није могуће учинити. У супротном, све комбинације можемо поделити на оне које почињу најмањим елементом скупа од $n$ елемената и на оне који не почињу њиме. Можемо дакле, узети најмањи елемент скупа и затим гледати све могуће начине да се одабере $k − 1$ елемент из истог $n$-точланог скупа или можемо свих $k$ елемената изабрати из скупа из ког је избачен тај најмањи елемент. Овим добијамо веома једноставну рекуренту везу на основу које можемо имплементирати рекурзивну функцију:

$$\begin{aligned} f(n,k) = \begin{cases} 1, & \text{ за } k = 0 \\ 0, & \text{ за } к > 0 \\ f(n, k-1) + f(n-1, k), & \text{ за } k, n > 0 \end{cases} \end{aligned}$$

Имплементација директно следи из приказане рекурентне релације:

static int broj_kombinacija_sa_ponavljanjem(int n, int k)
{
    // провера базних случајева
    if (k == 0)
        return 1;
    if (n == 0 && k > 0)
        return 0;
    // рекурзивно одређујемо тражено решење
    return broj_kombinacija_sa_ponavljanjem(n, k-1) 
                + broj_kombinacija_sa_ponavljanjem(n-1, k);
}

Приказано рекурзивно решење је експоненцијалне временске сложености. Као и у претходном задатку можемо да искористимо мемоизацију да бисмо спустили временску сложеност. Решење зависи од два параметра $n$ и $k$, па за чување решења подпроблема можемо да искористимо $(n+1) \times (n+1)$ матрицу. Да бисмо мемоизацију могли да користимо на исправан начин, потребно је да осмислимо начин на који ћемо једнозначно разликовати већ решене проблеме од оних које треба да решавамо. То ћемо постићи сагледавањем могућих вредности проблема. Решења проблема су вредности веће или једнаке од $0$, па проблеме које нисмо до сада решили можемо да обележимо са вредности $-1$. Мемоизовано решење је у наставку:

static int broj_kombinacija_sa_ponavljanjem(int n, int k, int[,] memo)
{
    // ако смо проблем већ решили, само враћамо решење
    if (memo[n, k] >= 0)
        return memo[n,k];
    // провера базног случаја. пре враћања вредности, уписујемо их
    // у помоћну матрицу
    if (k == 0)
        return memo[n,k] = 1;
    if (n == 0 && k > 0)
        return memo[n,k] = 0;
    // проблем решеавамо рекурзивно и решење уписујемо у 
    // помоћну матрицу
    memo[n,k] = broj_kombinacija_sa_ponavljanjem(n, k-1, memo) 
                    + broj_kombinacija_sa_ponavljanjem(n-1, k, memo);
    // враћамо решење
    return memo[n,k];
}
static int broj_kombinacija_sa_ponavljanjem(int n, int k)
{
    // креирамо помоћну матрицу
    int[,] memo = new int[n+1, n+1];
    // на почетку нисмо решили ниједан проблем,
    // па иницијализујемо вредности матрице на -1
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            memo[n,k] = -1;
    // на крају, решавамо проблем
    return broj_kombinacija_sa_ponavljanjem(n,k,memo);
}

Елиминацију рекурзије можемо да урадимо пажљивом анализом начина на који се попуњава помоћна матрица. Број комбинација за разне вредности $(n, k)$ се може распоредити у правоугаоник.

$$\begin{matrix} (k,n) & & & & & & \\ (0,0) & (0,1) & (0,2) & (0,3) & (0,4) & (0,5) & \\ (1,0) & (1,1) & (1,2) & (1,3) & (1,4) & (1,5) & \\ (2,0) & (2,1) & (2,2) & (2,3) & (2,4) & (2,5) & \\ (3,0) & (3,1) & (3,2) & (3,3) & (3,4) & (3,5) & \\ (4,0) & (4,1) & (4,2) & (4,3) & (4,4) & (4,5) & \\ (5,0) & (5,1) & (5,2) & (5,3) & (5,4) & (5,5) & \end{matrix}$$

Пре него што наставимо, треба приметити да смо матрицу приказали транспоновано. Прецизније, параметар $k$ броји редове, док параметера $n$ броји колоне. Уместо функционалних позива у правоугаонику можемо приказати и конкретне вредности броја комбинација са понављањем за различите вредности параметара $(n, k)$:

$$\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & \\ 0 & 1 & 2 & 3 & 4 & 5 & \\ 0 & 1 & 3 & 6 & 10 & 15 & \\ 0 & 1 & 4 & 10 & 20 & 35 & \\ 0 & 1 & 5 & 15 & 35 & 70 & \\ 0 & 1 & 6 & 21 & 45 & 126 & \end{matrix}$$

Претходна рекурентна веза нам говори да се у првој колони налазе нуле, у првој врсти јединице, а да је сваки елемент у остатку матрице једнак збиру елемената непосредно изнад и лево од њега. Матрицу можемо попунити врсту по врсту, чиме директно елиминишемо рекурзију и добијамо следеће итеративно решење:

static int broj_kombinacija_sa_ponavljanjem(int n, int k)
{
    // креирамо помоћну матрицу
    int[,] memo = new int[k+1, n+1];
    // иницијализујемо основни случај за k = 0 (први ред)
    for (int j = 0; j <= n; j++)
        memo[0,j] = 1;
    // попуњавамо остатак матрице
    for (int i = 1; i <= k; i++)
    {
        // основни случај (прва колона)
        memo[i,0] = 0;
        // попуњавамо унутрашњост матрице према формули        
        for (int j = 1; j <= n; j++)
            memo[i,j] = memo[i-1,j] + memo[i,j-1];
    }
    // враћамо решење
    return memo[k, n];
}

Приказано итеративно решење је могуће меморијски оптимизовати тако да не памтимо чутаву матрицу. Елементи сваке врсте зависе само од елемената те и претходне врсте, па није неопходно чувати целу матрицу, већ је довољно чувати само један низ, који ће током ажурирања чувати неке елементе претходне и неке елементе текуће врсте. Врста за следеће $k$ се може добити ажурирањем врсте за претходно $k$. Пошто сваки елемент у правоугаонику зависи од вредности изнад и лево од себе, врсту можемо ажурирати слева надесно. Инваријанта је да се у тренутку ажурирања позиције $n$, на позицијама строго мањим од $n$ налазе вредности из текуће врсте $k$, а на позицијама од $n$ надаље се налазе вредности из претходне врсте $k − 1$. Елемент на позицији $n$ који садржи вредност са позиције $(k − 1, n)$ правоугаоника увећавамо за вредност лево од њега који садржи вредност $(k, n−1)$ и тако добијамо вредност елемента на позицији $(k, n)$. Увећавањем вредности $n$ за $1$ се одржава инваријанта. Меморијски оптимизовано решење је у наставку:

static int broj_kombinacija_sa_ponavljanjem(int n, int k)
{
    // креирамо помоћни низ
    int[] memo = new int[n+1];
    // иницијализујемо основни случај за k = 0 (први ред)
    for (int j = 0; j <= n; j++)
        memo[j] = 1;
    // попуњавамо остатак матрице
    for (int i = 1; i <= k; i++)
    {
        // основни случај (прва колона)
        memo[0] = 0;
        // попуњавамо унутрашњост матрице, тј. реда према 
        // описаном поступку
        for (int j = 1; j <= n; j++)
            memo[j] += memo[j-1];
    }
    // враћамо решење
    return memo[n];
}

Временска сложеност меморијски оптимизованог решење је квадратна, а просторна сложеност је линеарна.

Задатак 4

Партиција позитивног природног броја $n$ је растављање броја $n$ на збир неколико позитивних природних бројева при чему је редослед сабирака небитан (стога можемо претпоставити да је тај редослед или увек нерастући или увек неопадајући). На пример, ако је редослед нерастући, партиције броја $4$ су $1 + 1 + 1 + 1$, $2 + 1 + 1$, $2 + 2$, $3 + 1$, $4$. Написати програм који одређује број партиција за дати природан број $n$.

Улаз: Прва и једина линија стандардног улаза садржи природан број $n$ $(n \leq 100)$.

Излаз: На стандардном излазу приказати у првој линији број партиција природног броја $n$.

Решење

Да бисмо решили задатак потребно је да прво осмислимо индуктивно-рекурзивни опис решења. Свака партиција има свој први сабирак. Свакој партицији броја $n$ којој је први сабирак $s$ (при чему је $1 \le s \le n$) једнозначно одговара нека партиција броја $n − s$. Наметнућемо услов да су сабирци у свакој партицији сортирани нерастуће. Зато, ако је први сабирак $s$, сви сабирци иза њега морају да буду мањи или једнаки од $s$. Зато нам није довољно само да умемо да пребројимо све партиције броја $n − s$, већ је потребно да ојачамо индуктивну хипотезу. Означимо са $p_{n,s_{max}}$ број партиција броја $n$ у којима су сви сабирци мањи или једнаки од $s_{max}$. Индуктивно-рекурзивна конструкција решења је следећа:

1. Базни случај - С обзиром да наше решење зависи од параметара $n$ и $s_{max}$, морамо да размотримо следеће случајеве:
   • Ако је $n=0$, тада постоји само једна партиција броја која не садржи сабирке. Дакле, важиће $p_{0,s_{max}} = 1$.
   • Ако је $n > 0$ и $s_{max} = 0$, тада не постоји ни једна партиција броја, јер од сабирака који су сви једнаки нули не можемо никако направити позитиван број. Дакле, важиће $p_{n,0} = 0$.
2. Индуктивна-хипотеза - Умемо да израчунамо $p_{n-1,s_{max}}$.
3. Индуктивни корак (конструкција) - Током израчунавања $p_{n,s_{max}}$ можемо да разматрамо два случаја. Први случај је да се цифра $s_{max}$ налази у збиру, тј. партицији и да се не налази у партицији. Јасно је да ће коначно решење бити збир ова два случаја. Дакле, решавамо следеће подпроблеме:
   • Ако се у збиру не јавља сабирак $s_{max}$, тада је највећи сабирак $s_{max} - 1$ и број таквих партиција је $p_{n,s_{max}-1}$
   • Други случај, тј. да је $s_{max}$ део збира, је могућ само ако је $n \ge s_{max}$. У том случају, број партиција ће бити $p_{n - s_{max}, s_{max}}$.

Одавде добијамо следећу рекурентни релацију:

$$\begin{aligned} f(n, s) = \begin{cases} 1, & \text{ за } n = 0 \\ 0, & \text{ за } n > 0, s = 0 \\ f(n, s-1), & \text{ за } n > 0, s > 0, n < s \\ f(n, s-1) + f(n-s, s), & \text{ за } n > 0, s > 0, n \ge s \end{cases} \end{aligned}$$

Рекурзивна имплементација следи директно из рекурентне релације:

static int broj_particija(int n, int s)
{
    // провера базних случајева
    if (n == 0)
        return 1;
    if (s == 0)
        return 0;
    // прво одређујемо број партиција без броја s (искључи)
    int br = broj_particija(n, s - 1);
    // затим, ако можемо укључујемо и изразе који садрже
    // број s (укључи)
    if (n >= s)
        br += broj_particija(n-s, s);
    // на крају, враћамо тражени резултат
    return br;
}
static int broj_particija(int n)
{
    // највећи сабирак који можемо да користимо 
    // је сам број n
    return broj_particija(n, n);
}

Приметимо да се у рекурентној релацији исти сабирак налази у два случаја. Тада се у имплементацији заједнички сабирак најчешће рачуна увек, а остали сабирци се рачунају само ако за тиме има потребе, што се види у линијама 9-12. Приказано решење је експоненцијално и може се лако учинити ефикаснијим применом мемоизације.

static int broj_particija(int n, int s, int[,] memo)
{
    // ако је проблем већ решен, само враћамо познато решење
    if (memo[n,s] != -1)
        return memo[n,s];
    // провера базних случајева и уписивање решења
    if (n == 0)
        return memo[n,s] = 1;
    if (s == 0)
        return memo[n,s] = 0;
    // прво одређујемо број партиција без броја s (искључи)
    // и решење памтимо за касније
    int br = broj_particija(n, s - 1, memo);
    // затим, ако можемо укључујемо и изразе који садрже
    // број s (укључи) и памтимо резултат
    if (n >= s)
        br += broj_particija(n-s, s, memo);
    // на крају, враћамо тражени резултат
    return memo[n,s] = br;;
}
static int broj_particija(int n)
{
    // креирамо помоћну структуру података у којој чувамо
    // решења подпроблема
    int[,] memo[n+1, n+1];
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            memo[i,j] = -1;
    // највећи сабирак који можемо да користимо 
    // је сам број n
    return broj_particija(n, n, memo);
}

Рекурзија се може лако елиминисати попуњавањем матрице ред по ред. Решење које користи динамичко програмирање на више је у наставку.

static int broj_particija(int n)
{
    // креирамо помоћну структуру података у којој чувамо
    // решења подпроблема
    int[,] memo[n+1, n+1];
    // базни случај n = 0 (први ред)
    for (int j = 0; j <= n; j++)
        memo[0,j] = 1;
    // попуњавамо остатак матрице
    for (int i = 1; i <= n; i++) 
    {   
        // базни случај (n > 0, s = 0)
        memo[i,0] = 0;
        // редом попуњавамо колоне 
        for (int j = 1; j <= n; j++)
        {
            // искључи - текући број ј (s_max) не користимо
            memo[i,j] = memo[i, j-1];
            // ако је број већи од текућег ј (s_max), онда 
            // ј (s_max) можемо да користимо у партицији
            if (i >= j) 
                memo[i,j] += memo[i - j, j];
        }
    }
    // највећи сабирак који можемо да користимо 
    // је сам број n
    return memo[n,n];
}

Попуњавање матрице ред по ред нас онемогућава да извршимо меморијску оптимизацију. Проблем се крије у линији 22. Наш текући резултат завици од резултата одмах поред њега (линија 18) и зависи од решења која се налази у истој колони, али изнад њега (линија 22). Проблем је у томе што се потребно решење не налази директно изнад, нити на фиксном растојању изнад за цео ред, већ је позиција елемента која нам треба променљива. Управо због тога, морамо у сваком тренутку да чувамо целу матрицу.

На овом месту није тешко уочити да меморијска оптмизација ипак може да се изврши променом начина на који матрицу обилазимо. Уколико бисмо матрицу попуњавали колону по колону, уместо ред по ред, тада не бисмо наишли на раније описани проблем. У овом случају, резултат $(i,j)$ би зависио од већ израчунатог решења у текућој колони $(i, j - s)$ и његове старе вредности из претходне колоне $(i,j-1)$. Дакле, могли бисмо да попуњавамо матрицу одозго на доле, слева на десно, што би нам омогућило да чувамо само једну колону уместо целу матрицу. Меморијски оптимизовано решење је у наставку:

static int broj_particija(int n)
{
    // креирамо помоћну структуру података у којој чувамо
    // решења подпроблема
    int[] memo[n+1];
    // базни случај n = 0 (први ред)
    memo[0] = 1;
    // попуњавамо остатак матрице
    for (int j = 1; j <= n; j++) 
    {   
        // редом попуњавамо колону по колону
        for (int i = 1; i <= n; i++)
        {
            memo[i] += memo[i - j];
        }
    }
    // највећи сабирак који можемо да користимо 
    // је сам број n
    return memo[n];
}

Задатак 5

Текст који се састоји само од великих слова енглеске абецеде је кодиран тако што је свако слово замењено његовим редним бројем у абецеди. На пример, текст $BABAC$ је кодиран низом цифара $21213$. Међутим, пошто између цифара није прављен размак, декодирање није једнозначно. На пример, $21213$ може представљати $BABAC$, али и $BAUC$, $BABM$, $BLAC$, $BLM$, $UBAC$, $UUC$, $UBM$. Написати програм који одређује број начина на који је могуће декодирати унети низ цифара.

Улаз: Прва линија стандардног улаза садржи низ цифара добијених кодирањем неког текста - низ има највише $100$ цифара.

Излаз: На стандардни излаз исписати број начина да се тај низ декодира (претпоставити да тај број може да стане у $64$-битан неозначен цео број).

Решење

Ако кренемо да разматрамо низ цифара од његовог почетка, можемо да издвојимо његову прву цифру, да је декодирамо и затим да декодирамо суфикс добијен његовим уклањањем, или да издвојимо прве две цифре, декодирамо њих и затим да декодирамо суфикс добијен њиховим уклањањем. Први начин је могућ ако низ није празан и ако је прва цифра различита од нуле, док је други могућ ако низ има бар две цифре, ако је прва цифра различита од нуле, а те две цифре граде број између $1$ и $26$. Ово сугерише рекурзивно решење у којем је параметар рекурзије позиција $i$, а рекурзивна функција враћа број начина да се декодира суфикс који почиње на позицији $i$. Излаз из рекурзије је случај празног низа $(i = n)$ који се може декодирати на један једини начин (празном ниском).

У овом рекурзивном решењу постојаће веома извесно велики број идентичних рекурзивних позива (тј. по- зива за исту вредност улазног низа). Нпр. ако низ почиње са $11$ тада ће се његов суфикс разматрати и када се посебно декодира свака од јединица и када се декодира пар цифара који гради број $11$. Ово доводи до непотребног увећања сложености, а као што знамо, решење долази у облику динамичког програмирања.

Индуктивно-рекурзивно решење је у наставку:

static int broj_dekodiranja(char[] niz, int i)
{
    // ако смо стигли до краја низа, успешно смо декодирали бар један низ
    if (i == niz.Length)
        return 1;
    // ако стринг почиње цифром нула, то не може бити валидно слово
    if (niz[i] == 0)
        return 0;
    // декодирамо почетну цифру и број декодирања је једнак броју
    // декодирања суфикса
    int br = broj_dekodiranja(niz, i + 1);
    // одређујемо број преосталих слова
    int preostaloSlova = niz.Length - i;
    // ако можемо да декодирамо две цифре, декодирамо их и увећамо
    // број декодирања за број декодирања суфикса без тих цифара
    if (preostaloSlova >= 2 && (10*niz[i] + niz[i+1]) <= 26)
        br += broj_dekodiranja(niz, i + 2);
    // на крају, враћамо резултат. 
    return br;
}
static int broj_dekodiranja(string s)
{
    // стринг пребацујемо у низ
    char[] niz = s.ToCharArray();
    // пребацујемо вредности у низу на интервал 0-9
    for (int i = 0; i < niz.Length; i++)
        niz[i] -= '0';
    // враћамо решење проблема 
    return broj_dekodiranja(niz, 0);
}

Приказано решење се директно мемоизује уз помоћ низа.

static int broj_dekodiranja(char[] niz, int i, int[] memo)
{
    // ако смо проблем већ решавали, само враћамо решење
    if (memo[i] != -1)
        return memo[i];
    // ако смо стигли до краја низа, успешно смо декодирали бар један низ
    if (i == niz.Length)
        return memo[i] = 1;
    // ако стринг почиње цифром нула, то не може бити валидно слово
    if (niz[i] == 0)
        return memo[i] = 0;
    // декодирамо почетну цифру и број декодирања је једнак броју
    // декодирања суфикса
    int br = broj_dekodiranja(niz, i + 1, memo);
    // одређујемо број преосталих слова
    int preostaloSlova = niz.Length - i;
    // ако можемо да декодирамо две цифре, декодирамо их и увећамо
    // број декодирања за број декодирања суфикса без тих цифара
    if (preostaloSlova >= 2 && (10*niz[i] + niz[i+1]) <= 26)
        br += broj_dekodiranja(niz, i + 2, memo);
    // на крају, враћамо резултат. 
    return memo[i] = br;
}
static int broj_dekodiranja(string s)
{
    // стринг пребацујемо у низ
    char[] niz = s.ToCharArray();
    // пребацујемо вредности у низу на интервал 0-9
    for (int i = 0; i < niz.Length; i++)
        niz[i] -= '0';
    // креирамо и иницијализујемо помоћну структуру
    int[] memo = new int[niz.Length + 1];
    for (int i = 0; i < memo.Length; i++)
        memo[i] = -1;
    // враћамо решење проблема 
    return broj_dekodiranja(niz, 0, memo);
}

Нека $d_i$ представља број начина да се декодира суфикс речи $s$ који почиње на позицији $i$ (укључујући и њу). С обзиром на структуру рекурзије, низ $d_i$ можемо одредити сдесна налево. $d_n$ представља број начина да се декодира празан суфикс, а то је $1$. У супротном у низу имамо бар једну цифру.

Ако је $s_i = 0$, тада је $d_i = 0$ (тада ни први, ни други начин декодирања нису могући). У супротном, треба да размотримо могућност декодирања на први и на други начин. Први начин је увек применљив (јер суфикс почиње бар једном цифром $s_i$ за коју смо утврдили да није цифра $0$) и у том случају низ можемо декодирати на $d_{i+1}$ начина. Други начин је применљив ако имамо бар две цифре (ако је $i < n − 1$) и ако је број добијен од цифара $s_i$ $s_{i+1}$ (за $s_i$ смо утврдили да није цифра $0$) између $1$ и $26$ и у том случају је број начина декодирања добијен на овај начин једнак $d_{i+2}$. Једноставности ради $d_{n−1}$ је могуће одредити посебно, да се не би стално проверавало да ли је $i < n − 1$.

Дакле, $d_n = 1$, $d_{n−1} = 0$ ако је $s_{n−1} = 0$, $d_{n−1} = 1$ ако је $s_{n−1} = 0$. За све вредности $i$ од $n − 2$ унатраг важи да је $d_i = 0$ ако је $s_i = 0$, да је $d_i = d_{i+1}$ , ако $s_i$ $s_{i+1}$ дају број који није између $1$ и $26$, тј. $d_i = d_{i+1} + d_{i+2}$ ако $s_i$ $s_{i+1}$ дају број који јесте између $1$ и $26$.

Решење добијено елиминацијом рекурзије је у наставку:

static int broj_dekodiranja(string s)
{
    // стринг пребацујемо у низ
    char[] niz = s.ToCharArray();
    // пребацујемо вредности у низу на интервал 0-9
    for (int i = 0; i < niz.Length; i++)
        niz[i] -= '0';
    // креирамо и иницијализујемо помоћну структуру
    int[] memo = new int[niz.Length + 1];
    // иницијализујемо базне случајеве
    memo[n] = 1;
    memo[n-1] = niz[n-1] != 0 ? 1 : 0;
    // низ реконструишемо уназад
    for (int i = n - 2; i >= 0; i--)
    {
        // ако је текућа цифра 0, онда не можемо да урадимо декодирање
        if (niz[i] == 0)
            memo[i] = 0;
        // ако није нула
        else 
        {
            // онда је број декодирања једнак броју декодирања суфикса
            memo[i] = memo[i+1];
            // ако можемо да је објединимо са следећом цифром, то чинимо
            if (10*niz[i] + niz[i+1] <= 26)
                memo[i] += memo[i+2];
        }
    }
    // враћамо решење проблема 
    return memo[0];
}

Приметимо да је за одређивање сваке претходне вредности низа $d$ потребно знати само њене две наредне вредности. Стога није неопходно чувати цео низ, већ је у сваком тренутку потребно познавати само две његове узастопне вредности (кренувши од последње и претпоследње). Одавде директно следи меморијска оптимизација:

static int broj_dekodiranja(string s)
{
    // стринг пребацујемо у низ
    char[] niz = s.ToCharArray();
    // пребацујемо вредности у низу на интервал 0-9
    for (int i = 0; i < niz.Length; i++)
        niz[i] -= '0';
    // иницијализујемо базне случајеве
    int memo2 = 1;
    int memo1 = niz[n-1] != 0 ? 1 : 0;
    // низ реконструишемо уназад
    for (int i = n - 2; i >= 0; i--)
    {
        // текуће решење
        int memo = 0;
        // ако је текућа цифра 0, онда не можемо да урадимо декодирање
        if (niz[i] == 0)
            memo = 0;
        // ако није нула
        else 
        {
            // онда је број декодирања једнак броју декодирања суфикса
            memo = memo1;
            // ако можемо да је објединимо са следећом цифром, то чинимо
            if (10*niz[i] + niz[i+1] <= 26)
                memo1 += memo2;
        }
        memo2 = memo1;
        memo1 = memo;
    }
    // враћамо решење проблема 
    return memo1;
}

Задатак 6

Написати програм којим се за две дате ниске $x$ и $y$, одређује број појављивања ниске $y$ као подниза ниске $x$. Ниска $y$ је подниз ниске $x$ ако се може добити од ниске $x$ брисањем произвољног броја карактера.

Улаз: Прва линија стандардног улаза садржи ниску $x$, а друга линија ниску $y$. Дужине ниски су највише $100$ карактера.

Излаз: На стандардном излазу приказати само број појављивања ниске $y$ као подниза ниске $x$.

Решење

Размотримо прво рекурзивно решење. Ако су обе ниске непразне, тада се може упоредити њихово последње слово. Aко су им последња слова различита онда је укупан број појављивања подниза једнак броју појављи- ваља у префиксу прве ниске без последњег карактера, а ако су им последња слова једнака, онда је укупан број појављивања једнак том броју увећаном за број појављивања префикса друге ниске без последњег карактера у префиксу прве ниске без последњег карактера. Базу чине случајеви када је нека ниска празна. Ако је друга ниска празна тада се онда једном јавља као подниз прве ниске, а ако је прва ниска празна (а друга није) тада она не садржи подниз који одговара другој ниски. Пошто се кроз рекурзију стално разматрају префикси ниски, ниске не морамо мењати кроз рекурзију, већ можемо прослеђивати само дужине префикса (нека је $n$ дужина префикса прве, а $m$ дужина префикса друге ниске). Ако је $f(n,m)$ тражени број појављивања, тада важи:

$$\begin{aligned} f(n,m) = \begin{cases} 1, & \text{ за } m = 0 \\ 0, & \text{ за } n = 0, m > 0 \\ f(n-1, m) + f(n-1, m-1), & \text{ за } n,m > 0, x_n = y_m \\ f(n-1, m), & \text{ за } n,m > 0, x_n \ne y_m \end{cases} \end{aligned}$$

На основу овога је веома једноставно направити рекурзивну имплементацију.

static int broj_pojavljivanja(string x, string y, int n, int m)
{
    // провера основних случајева
    if (m == 0)
        return 1;
    if (n == 0)
        return 0;
    // одређујемо број појављивања без последњег карактера (искључи)
    int br = broj_pojavljivanja(x, y, n-1, m);
    // ако су последњи карактери исти, онда гледамо појављивања префикса 
    if (x[n] == y[m])
        // на постојеће решење додајемо број појављивања префикса (укључи)
        br += broj_pojavljivanja(x, y, n - 1, m - 1);
    // враћамо резултат
    return br;
}
static int broj_pojavljivanja(string x, string y)
{
    return broj_pojavljivanja(x, y, x.Length - 1, y.Length - 1);
}

С обзиром на то да ће се у наивној рекурзивној имплементацији исти рекурзивни позиви извршавати више пута, таква имплементација биће неефикасна. Ефикасност се лако може поправити техником динамичког програмирања. Мемоизовано решење је у наставку:

static int broj_pojavljivanja(string x, string y, int n, int m, int[,] memo)
{
    // ако смо проблем већ решавали, само вратимо од раније познато решење
    if (memo[n,m] != -1)
        return memo[n,m];
    // провера основних случајева
    if (m == 0)
        return memo[n,m] = 1;
    if (n == 0)
        return memo[n,m] = 0;
    // одређујемо број појављивања без последњег карактера (искључи)
    int br = broj_pojavljivanja(x, y, n-1, m, memo);
    // ако су последњи карактери исти, онда гледамо појављивања префикса 
    if (x[n] == y[m])
        // на постојеће решење додајемо број појављивања префикса (укључи)
        br += broj_pojavljivanja(x, y, n - 1, m - 1, memo);
    // враћамо резултат
    return memo[n,m] = br;
}
static int broj_pojavljivanja(string x, string y)
{
    // помоћна структура података у којој чувамо решења подпроблема
    int[,] memo = new int[x.Length, y.Length];
    // иницијализујемо вредности у помоћној структури
    for (int i = 0; i < x.Length; i++)
        for (int j = 0; j < y.Length; j++)
            memo[i,j] = -1;
    // решавамо проблем и враћамо резултат
    return broj_pojavljivanja(x, y, x.Length - 1, y.Length - 1, memo);
}

Елиминацију рекурзије можемо лако извршити. Пошто елемент на позицији $(n,m)$ зависи од елемената на позицијама $(n−1,m)$ и $(n−1,m−1)$, матрицу можемо попуњавати било врсту по врсту, било колону по колону.

static int broj_pojavljivanja(string x, string y)
{
    // помоћна структура података у којој чувамо решења подпроблема
    int[,] memo = new int[x.Length, y.Length];
    // основни случај
    memo[0,0] = 1;
    for (int j = 1; j < y.Length; j++)
        memo[0,j] = 0;
    // попуњавамо матрицу
    for (int i = 1; i < x.Length; i++)
    {
        // основни случај
        memo[i,0] = 1;
        for (int j = 1; j < y.Length; j++)
        {
            // случај без последњег слова
            memo[i,j] = memo[i-1,j];
            // ако су последња слова иста, онда гледамо префикс
            // који их не укључује. 
            if (x[j] == y[j])
                memo[i,j] += memo[i-1, j-1];
        }
    }
    // враћамо резултат
    return memo[x.Length-1, y.Length-1];
}

Меморијска оптимизација се такође може лако урадити. Ако претпоставимо да попуњавамо врсту по врсту матрице можемо извршити меморијску оптимизацију тако што само чувамо елементе једне врсте. У првој врсти иницијализујемо све елементе на нулу, осим првог који иницијализујемо на јединицу. Приликом преласка са текуће на наредну врсту, ажурирање можемо вршити с десна на лево. Ако су одговарајући карактери ниски једнаки, тада текући елемент увећавамо за њему претходни.

static int broj_pojavljivanja(string x, string y)
{
    // помоћна структура података у којој чувамо решења подпроблема
    int[] memo = new int[y.Length];
    // основни случај
    memo[0] = 1;
    // попуњавамо матрицу
    for (int i = 1; i < x.Length; i++)
    {
        for (int j = 1; j < y.Length; j++)
        {
            // ако су карактери исти, ажурирамо према правилу
            if (x[j] == y[j])
                memo[j] += memo[j-1];
        }
    }      
    // решавамо проблем и враћамо резултат
    return memo[y.Length-1];
}