After a long time of trying to solve this problem, I was excited to finally have a solution that seemed to work.
I quickly submitted the solution, but to my great surprise, I obtained a TLE. I quickly searched through the code for anything suspicious, but I could not find anything — it seems to be very clearly O(n^2), with n at most 5000... but it still takes far too long: running it on my computer it seemed to take more than 1 second for the loop where I simply initialize all the values to Infinity!
Does anybody know why it would take so long to do such a simple task as this? What am I missing here?
try swap last dimension with first one.
Then you will have 2 * n * ( (n+3)/2 ) instead of n * ( (n + 3) / 2) * 2
In your case you have too many arrays, for Java is really important.
I didnt read code much, but if you can reduce the number of layers of dp, it will help. (Or write the same code on C++, it should pass TL :) )
Interesting, I didn't realize that this would cause slowdown. I implemented your suggestion and then did an algorithm adjustment to half number of operations and managed to squeeze it in with 966 ms. (It still feels a bit slow, though) I suppose that, in general, it's best to have the largest dimension be the last one in an array, though I'm used to seeing the smallest one at the end for some reason. Thanks a lot for your help!
too many cache hits,try swapping dimensions
Do you mean cache miss?
ohh yes sorry
Anyway, I can't identify any potential for lots of cache misses in the OP's code. Could you identify which part causes the cache misses?