Dlaczego tak jest i jak naprawić spowolnienie tego programu.
Używając referencję.
Teraz ta memoizacja prawie w ogóle nie działa, bo kopiujesz całą hashmapę do każdej nowej warstwy rekursji, co nie tylko jest wolne samo z siebie, ale też sprawia że nie zapamiętujesz wyników.
To znaczy, robiąc `uniquePaths(m - 1, n, memoization) + uniquePaths(m, n - 1, memoization)`, cokolwiek zostało zapamiętane w pierwszym `uniquePaths`, nie trafia do drugiego.
Po drugie,
string key;
Nie wiem czemu koniecznie chciałeś mieć zmienną globalną (jak one w ogóle nie powinny być używane), ale właśnie ten globalny stan Ci kompletnie rozwala program. Zastanów się nad tym:
// tutaj ustawiasz wartosc dla `key`
key = to_string(m) + ',' + to_string(n);
// te funkcje w srodku ustawiaja jakas inna wartosc dla `key`
memoization[key] = uniquePaths(m - 1, n, memoization) + uniquePaths(m, n - 1, memoization);
// wiec tutaj wcale nie uzywasz tego oryginalnego `key` z gory, tylko tego co ustawily rekurencyjne funkcje
return memoization[key];
Zamień to na zmienną lokalną i powinno być wszystko ok.
(Po trzecie, jeśli wciąż będziesz mieć problemy wydajnościowe, to zamiast tworzyć stringa to używaj bardziej bezpośrednio te dwie liczby jako klucz mapy)