Drum3

O prima solutie pentru aceasta problema ar fi o dinamica in N3, din[i][j][k] = numarul total de drumuri pentru a ajunge in pozitia i, j din matrice cu k schimbari de directie. Aceasta solutie este totusi ineficienta. Pentru a gasi o solutie in N2, vom face cateva observatii:

  • Numarul total de posibilitati este egal cu dublul numarului de posibilitati daca am face prima mutare la dreapta (drumurile sunt simetrice fata de prima diagonala). Asadar de acum inainte vom considera ca prima mutare va fi mereu la dreapta, iar la sfarsit inmultim cu doi rezultatul.
  • Orice drum de la 1, 1 la N, N in matrice este compus dintr-o serie de segmente verticale (ce unesc doua casute adiacente) ce au suma lungimilor egala cu N-1 si o serie de segmente orizontale cu aceeasi proprietate.
  • Numarul acestor segmente verticale si orizontale este unic determinat de K. Fie No si Nv numarul de segmente orizontale si respectiv verticale, atunci No = (K + 2) / 2 si Nv = (K + 1) / 2.
  • Numarul posibilitatilor de a parcurge matricea cu exact K schimbari de directie este egal cu numarul de partitionari a numarului N-1 in No numere inmultit cu numarul de partitionari a numarului N-1 in Nv numere, unde definim numarul de partitionari al numarul N in K sume ca fiind numarul total de moduri in care putem obtine suma N cu K numere naturale unde ordinea conteaza (exemplu: partitionarile lui 4 in 3 numere sunt: 1 + 1 + 2, 1 + 2 + 1 si 2 + 1 + 1).

Tot ce ramane de facut este sa vedem cum aflam numarul de partitionari al unui numar N in K numere. Daca ne gandim la numarul N ca la un segment de lungime N observam ca o partitionare a lui, in K numere poate fi reprezentata prin taierea segmentului in exact K segmente mai mici. Acest lucru se obtine prin K-1 taieturi in N-1 locuri posibile (exemplu: 2 + 3 + 1 poate fi reprezentat ca --|---|-). Asadar numarul de partitionari al unui numar N in K numere este egal cu combinari de N-1 luate cate K-1. De aici se deduce usor ca rezultatul final al problemei este C[N-2][No-1] * C[N-2][Nv-1] * 2 (unde C[x][y] este egal cu combinari de x luate cate y).