Please explain algo faster than N^4

I know dp algorithm, but it is too slow - O(N^4).

Please explain faster algorithm.

Re: Please explain algo faster than N^4

Posted by

AterLux 23 May 2011 12:16

Here algorithm O(1): use precalculated array ;)

Re: Please explain algo faster than N^4

Thank you)

Re: Please explain algo faster than N^4

It is possible to use a different DP state and calculate each of N^2 cells in O(N) time (N^3 DP algorithm)