h2. Walk the Talk
Vom rezolva independent problema pentru fiecare cuvant aflat in dictionar. Vom nota $a{~i,j~}$ matricea cu litere, iar s{~i~} cuvantul pe care il analizam la un anumit moment, acesta avand lungimea {$L$}. Vom construi matricea $sum{~i,j,k~}$ in care se va retine numarul de moduri in care se obtine secventa $s{~1~}, s{~2~}, ... , s{~k~}$ folosind doar dreptungiul cu colturile in ({$1,1$}) si ({$i,j$}) din matricea de litere. Pentru a calcula configuratia ({$i,j,k$}) se numara intai cate se obtin pentru secventa $1..k$ pentru dreptunghiul respectiv fara a considera casuta $(i,j)$ ({$sum{~i-1,j,k~}+sum{~i,j-1,k~}-sum{~i-1,j-1,k~}$}) apoi daca avem $a{~i,j~}=s{~k~}$ adunam cate solutii avem pentru secventa $1..k-1$ pentru dreptunghiul respectiv mai putin casuta $(i,j)$ ({$sum{~i-1,j,k-1~}+sum{~i,j-1,k-1~}-sum{~i-1,j-1,k-1~}$}). In final solutia se va afla in {$sum{~n,m,L~}$}. Complexitatea construirii fiecare configuratii in parte este $O(1)$ deci in total va fi {$O(n*m*L)$}. Memoria necesara este {$O(n*m*L)$}, dar aceasta se poate reduce la $O(n*m)$ daca luam in considerare faptul ca la fiecare moment ne este necesar doar numarul de solutii pentru o secventa cu $1$ mai mica.
Vom rezolva independent problema pentru fiecare cuvant aflat in dictionar. Vom nota a[i][j] matricea cu litere, iar s[i] cuvantul pe care il analizam la un anumit moment, acesta avand lungimea L. Vom construi matricea sum[i][j][k] in care se va retine numarul de moduri in care se obtine secventa s[1], s[2], ... , s[k] folosind doar dreptungiul cu colturile in (1,1) si (i,j) din matricea de litere. Pentru a calcula configuratia (i,j,k) se numara intai cate se obtin pentru secventa 1..k pentru dreptunghiul respectiv fara a considera casuta [i][j] (sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]) apoi daca avem a[i][j]=s[k] adunam cate solutii avem pentru secventa 1..k-1 pentru dreptunghiul respectiv mai putin casuta [i][j] (sum[i-1][j][k-1]+sum[i][j-1][k-1]-sum[i-1][j-1][k-1] ). In final solutia se va afla in sum[n][m][L]. Complexitatea construirii fiecare configuratii in parte este O(1) deci in total va fi O(n*m*L). Memoria necesara este O(n*m*L), dar aceasta se poate reduce la O(n*m) daca luam in
considerare faptul ca la fiecare moment ne este necesar doar numarul de solutii pentru o secventa cu 1 mai mica.
