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:

include include

using namespace std;

static int maximum = 0;

void sumPath(vector<vector> &triangleRows, int lastRow, int curRow, int curIndex, int acc) { int accumulate = triangleRows[curRow][curIndex] + acc;

if (curRow == lastRow) //Finished adding?
{
    if (accumulate > maximum) maximum = accumulate;
    return;
} //base case

for (int i = 0; i <= 1; i++) //Check next two down
{
    sumPath(triangleRows, lastRow, curRow+1, curIndex+i, accumulate); //cur+next
}

}

int main() { ifstream inf("numtri.in"); ofstream outf("numtri.out"); int rows; inf >> rows; vector<vector> triangleRows; triangleRows.reserve(rows); for (int i = 1; i <= rows; i++) //Create rows { //Create row vector row; row.reserve(i); for (int x = 0; x < i; x++) { int element; inf >> element; row.push_back(element); } triangleRows.push_back(row); }

sumPath(triangleRows, rows-1, 0, 0, 0);

outf << maximum << endl;
return 0;

}