Yes, I only have an NxN array which I memoize on, and each value is computed from other values in O(1) time, so it's O(n^2) at most. The slowness was because of some prewritten code to read the input (I parsed each line into a vector<int>... which I allocated *inside* my loop, so lots of overhead). I just replaced that with sscanf and resubmitted and I now have the fastest time.Adrian Kuegel wrote:Joe, are you sure you solve it in O(n^2)? Because I thought my algorithm is O(n^3), but my program is faster than your program. Did you also sum up the values of the matrix and store them?
If you're using O(n^3) but only have an O(n^2) array (like dh3014), then maybe you are probably trying to do it iteratively. For DP problems sometimes I find it's easier to come up with the best recurrence if I think about a memoization solution. Here's the recurrence I used:
ways[value][coin] = ways[value-coin][coin] + ways[value][coin-1]
Where value is the sum you're trying to make, and coin is the biggest coin you're allowed to use.