xenoslash's blog

DP Table with incomplete keys
By xenoslash, 11 years ago, In English

I have been struggling with a problem that involves DP. Usually, for dp problems, it's enough for me to just create arrays like int[][][][] dp, where a state can be indexed by the value of 4 integers. Just to be very concrete, let's say that dp[a][b][c][d] stores the minimum time to eat 'a' food of type 1, 'b' food of type 2, and so on. However, if the problem statement states that the amount of each food type ranges from 0 to 1000, it's no longer possible to store the table. But what if.. the restriction is that a+b+c+d <= 1000?

I use Java, and I tried using a Map. I made a wrapper class called Key that just stores int[4] foodAmounts, overrode hashCode, equals, and this allows me to have Map<Key, Integer> to store my dp values. However, whenever I want to access the map, I would have to create a new Key object. I might have to create multiple Key objects that correspond to the same array, and this eats up the memory. Is there a way to reuse these Key objects? E.g a function Key toKey(int[] arr) that returns the same object instance when given equivalent arrays.

I thought that solving this problem requires me to create a Map that stores a mapping between int[]arr and its unique Key object... but isn't this a recursive problem then? Since I need to make a Key out of int[] arr...

Thanks!

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Although I doubt that DP is the best technique for that problem, you may want to make the hashCode() method of the Key class depend on its array (foodAmounts) attribute. One way to to do is to return Arrays.hashCode(foodAmounts) which should practically return a unique hashes for unique arrays (same length and elements).

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry about this. I must have made a huge mistake somewhere that caused me to think that creating these Key objects will result in poor performance. Last AC code with creating new objects everytime I query: http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1235414

As for my previous submission in my other comment.. it's very wrong.. I had to reread what hashcodes are to make sure.

TL;DR: Plain old hashmap with wrapper class as keys are fine, even if the key objects get recreated for the same int[][][][] array.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, if you want to create a 4D int array of size a × b × c × d, you may do following (C-like pseudocode):

int *data = malloc(a * b * c * d);

Then, to access element (x, y, z, u), use this:

int *element = &data[(a * b * c) * u + (a * b) * z + (a) * y + x];

It should be pretty obvious how to expand this to any number of dimensions.

Note that, even if a + b + c + d ≤ 1000, abcd might reach approximately 4 × 109, so making an a × b × c × d array might be completely impossible in the task referenced.

→ Reply