#use hashmap or array waz
vital totem
maps + doubly linked list (create a class for doubly linked list)
Array doesn’t allow O(1) deletion in the middle
pale trench
python cache just attaches a hashmap to the function lol
it wraps the function in another function that first checks if the parameters are in the hashmap
if it is, return the cached value
wary robin
yeah the problem is
i couldnt figure out how to make an n dimensional hashmap within the time period
In c++
bc my dp function was 2 or 3 dimensional
2 or 3 arguments
nova yarrow
in java, you can create a class with those arguments as instance variables, then override the hashCode and equals method so that it's hashable
nova yarrow
yes java is best
wary robin
why else is java good
nova yarrow
yes java is best
wary robin
thanks
vital totem
What are you trying to do exactly? I didn’t understand
wary robin
You know what the @wide wolf decorator in python does right
I was tryna do that
cause i was using c++ but always do leetcode in python
vital totem
got it, i guess you can do the same thing in c++ but probably just use a map<vector<int>, int> and check for the arguments in the map to see if it has a computed value and return the value if it exists. Pass the map around as a reference in the function. Like:
void dp(map<vector<int>, int>& mp, ... other args) {}
@wary robin
this will avoid unnecessary copying for the map and works like the cache decorator in python
If there were only 2 arguments, you could've used a pair<int, int> instead of a vector<int> as the key
wary robin
If there were only 2 arguments, you could've used a pair<int, int> instead of a ...
I tried pair but i couldnt hash it as the key and didnt know how to make my own hash function
vital totem
you probably used unordered_map
wary robin
yea
vital totem
if you used map, it doesn't require hashing
wary robin
really
vital totem
its a little slow, but works for most cases
vital totem
yes
wary robin
but log n is very smlal anyway
vital totem
yeah