Pytanie - CanSum

Question

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int canSum(int TargetSum, vector<int> numbers,unordered_map<int,int> memo) {
	if (memo.find(TargetSum) != memo.end()) return memo[TargetSum];
	if (TargetSum == 0) return true;
	if (TargetSum < 0) return false;
	for (int x : numbers) {
		int remainder = TargetSum - x;
		if (canSum(remainder, numbers, memo)) {
			memo[TargetSum] = true;
			return true;
		}
	}
	memo[TargetSum] = false;
	return false;
}

int main()
{
	unordered_map<int, int> memo;
	/*cout << canSum(7, { 2,3 }, memo) << '\n';
	cout << canSum(7, { 5,3,4,7 }, memo) << '\n';
	cout << canSum(7, {2, 4 }, memo) << '\n';
	cout << canSum(8, {2,3,5}, memo) << '\n';*/
	cout << canSum(300, {7,14}, memo) << '\n';
}

Witam, napisałem kod, który powinien być szybszy i wykonywać ostatni element w szybszym czasie, używając mapy która przechowuje nam pewne wartości, jednak program nie wyświetla ostatniego zapytania zbyt szybko. Co mogłem przeoczyć?

Answer 1

Za każdym razem przesyłasz kopię mapy a nie referencję do niej.

Comments

Dokładnie i złożonnośc ci bardzo spada

---

Panowie, uratowaliście mi życie! Dzięki wielkie.

Czy jak nie mam refernecji do vectora to też mu tutaj złożonośc spada?

---

On go kopiuje całego wtedy.

Możesz albo wyciągnąc vector i mapę przed maina i wtedy masz globalny, najszybciej

Albo właśnie referencję przekazać.

W programowaniu konkursowym np. OI, OIJ, potyczki itp. zazwyczaj robi się większość globalnie, żeby się nie męczyć.

---

Ej bo jednak sprawdzam jeszcze raz poprawność tego problemu, i wychodzi inny wynik gdy daję referencję niż kopiuję go. W czym może być problem?

Edit : Muszę clearować mapę po każdym pytaniu

---

Takie tam prowizoryczne rozwiązanie:

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int canSum(int TargetSum, const vector<int>& numbers, unordered_map<int, int>& memo) {
    if (memo.find(TargetSum) != memo.end()) return memo[TargetSum];
    if (TargetSum == 0) return true;
    if (TargetSum < 0) return false; 
    for (int x : numbers) {
        int remainder = TargetSum - x;
        if (canSum(remainder, numbers, memo)) {
            memo[TargetSum] = true;
            return true;
        }
    }

    memo[TargetSum] = false;
    return false;
}

int canSum(int TargetSum, const vector<int>& numbers) {
    unordered_map<int, int> memo;
    return canSum(TargetSum, numbers, memo);
}

int main()
{
    cout << canSum(7, { 2,3 }) << '\n';
    cout << canSum(7, { 5,3,4,7 }) << '\n';
    cout << canSum(7, {2, 4 }) << '\n';
    cout << canSum(8, {2,3,5}) << '\n';
    cout << canSum(300, { 7,14 }) << '\n';
}

Może warto zrezygnować z rekurencji.

---

Jeśli chcesz mieć tę memoizację, to deklaruj mapę statycznie w funkcji. C++ gwarantuje inicjalizację jej przy pierwszym wejściu.