Zadanie Unique Paths

Question

Cześć, mam pytanie dotyczące tego kodu. Jest to podejście do rozwiązania zadania typu https://leetcode.com/problems/unique-paths/description/ . To jest kod w javascript, ale chciałem napisać to w c++. Mamy tutaj klucz, który redukuje nam w niektórych przypadkach złożoność. Tylko tutaj mamy klucz m,n i takim sposobem redukujemy powtarzające się sekwencje m i n. Z tego co wiem to ten kod redukuje też sekwencje n i m( odwrotne do m i n). Jednak nie do końca rozumiem jakim sposobem i czy na prawdę redukuje te odwrotne sekwencje. Brakuje mi to do zrozumienia jak napisać to w c++.

Answer 1

To działanie rekurencyjne
spójrz np na ten przykład 

class Solution {
public:
    int nl, ml, dp[105][105];

    bool valid(int x, int y) {
        if(x < nl and y < ml) return true;
        else return false;
    }

    int solve(int i, int j) {
        if(!valid(i, j)) return 0;
        if(i >= nl-1 and j >= ml-1) return 1;
        if(dp[i][j] != -1) return dp[i][j];
        int ans = solve(i+1, j) + solve(i, j+1);
        return dp[i][j] = ans;
    }

    int uniquePaths(int m, int n) {
        nl = m, ml = n;
        memset(dp, -1, sizeof(dp));
        int ans = solve(0, 0);
        return ans;
    }
};

spójrz na linie memo[key] = której przypisywane są wyniki kolejno rekurencyjnych wywołan przeszukiwania  coś na bazie drzewa, lub grafi w którym postępujesz zmniejszając zarówno klucz m jak klucz n 

Comments

Czyli, gdy mam przypadek 3,1 to zapisuję w kluczu 3,1 bez 1,3 bo później prawdopodobnie na niego natrafię?

---

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;
string key;

int uniquePaths(int m,int n, unordered_map<string, int> memoization) {
	key = to_string(m) + ',' + to_string(n);
	if (memoization.find(key) != memoization.end()) return memoization[key];
	if (m == 1 && n == 1)
		return 1;
	if (m == 0 || n == 0)
		return 0;
	memoization[key] = uniquePaths(m - 1, n, memoization) + uniquePaths(m, n - 1, memoization);
	return memoization[key];
}

int main()
{
	int m, n;
	cin >> m >> n;
	unordered_map<string, int> memoization;
	cout << uniquePaths(m, n,memoization) << '\n';
	return 0;
}

Starałem się napisać ten sam kod w c++, jednak nie działa on tak szybko.