3

I am working to solve a problem that is a bit similar to Euler Problem 215. I think I can explain this without explaining the entire problem and/or my full approach to solving it.

Right now I'm making recursive calls with RT([Arraylist of numbers], int i). As per the technique, I want to save the results, so if and when RT asks for the same problem, I can simple just look up the answer instead of recurring until the base case is reached.

Just to illustrate RT([3, 7.5, 10.5, 15], 2). In the recursion, the right in the right side to increment. The Arraylist is used to identify what else it needs to recall to the base case.

Usaully, my understanding of Dynamic Programming usually uses 2D Arrays where the results are saved and stored using what's being called as the reference point. This is great if it is something like RT(int x, int y). But what about my problem?

I guess I can change the ArrayList to a string 37510515 and then to some used ASCII numbers or perhaps the numbers itself. But I'm hoping I can approach this like a HashMap where I use the ArrayList as a key, but the flaw in this a HashMap only works well with one value (I know I can chain, but how would that work in storing results while easily keeping track of what "int i" it is called on?)

So in short, can anyone help me think of a way to store results with an ArrayList and an int as the two references?

Thanks in advance!

Zero Piraeus
  • 56,143
  • 27
  • 150
  • 160
user1159243
  • 33
  • 3
  • is the arraylist of numbers always in the same order? does that matter? if not, then a b-tree would work, and would keep reads at a minimum. if you're lucky, you do 1 lookup. worst case, you have to run through (in your case) 5 levels of the tree. – jasonmclose Jan 19 '12 at 19:43

2 Answers2

2

You can use objects of any class you like as keys for a HashMap, and it will work if the object has defined equals() and hashCode() properly. These methods have already been implemented properly in ArrayList, so you should find that using ArrayLists as HashMap keys works perfectly well.

If you want to use an ArrayList and a number combined as a key for a HashMap, you could either define a class for this, implementing hashCode() and equals() in that class, or cheat a bit by making the number just the last entry in the arraylist.

It sounds like what you are doing is more like http://en.wikipedia.org/wiki/Memoization than dynamic programming, but it may get the job done - I guess that the Euler problem has been set to make it doable for the best technique - if that is memoization or dynamic programming you should find it is affordable. It that takes too long, then both of us have missed some more efficient method.

One way of speeding it up further would be to take advantage of symmetries in the problem - e.g. if your state corresponds to a row (or a column) of blocks, then that is essential the same state as the row with the same blocks laid out right to left instead of left to right, or bottom to top instead of top to bottom.

mcdowella
  • 19,301
  • 2
  • 19
  • 25
  • Thanks. I took your advice. I took the easy way out and just added the number to the ArrayList rather than create a new object and define its equals() and hashCode(). I would call it a small "hack" as I make use in a way that is not intended. But still, it works now. – user1159243 Jan 23 '12 at 18:48
0

One way to solve is to implement your own class wrapping both arraylist & int, writing hashCode and equals as mentioned here.

Using a byte array as Map key

Community
  • 1
  • 1
Rajendran T
  • 1,513
  • 10
  • 15