Hello all,
While going through the USACO training pages problem "Number Triangles", I used a recursive function to calculate the answer. You can see the problem statement here: http://train.usaco.org/usacoprob2?a=nOEpHRAhtUw&S=numtri
I used recursion to try and solve it, but ran into a timeout on test case 6:
> Run 6: Execution error: Your program (`numtri') used more than the allotted runtime of 1 seconds (it ended or was stopped at 1.715 seconds) when presented with test case 6. It used 4312 KB of memory.
I realized that with the test data at hand, it made sense that my program would timeout.
Data:
199 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ... [and more] ...
My question is, is it possible for me to optimize my recursive solution, or should I try to use a loop instead of recursion? All hints and advice would be appreciated. (No full solutions please.)
My code below (C++11):