Memoization-based puzzle solution - sums in a triangle I am trying to solve a problem at Codechef. As I am new to programming, I am not familiar with dynamic programming. However, I do know the basics of recursion and memoization. Hence I implemented a solution to the above mentioned problem. The problem with my solution is that it exceeds the time limit given. As far as I can guess, the problem seems to be with my memoization logic. Please help me optimize the code.

#include &lt;iostream&gt;
#include &lt;algorithm&gt;
#include &lt;vector&gt;
#include &lt;string&gt;

using namespace std;

typedef vector&lt;int&gt; vector1D ;
typedef vector&lt;vector1D &gt; vector2D ; // Two Dimensional vector

int rownum;
int noOfCalls = 0;
vector2D a;
vector2D cache; // The cache to implement memoization

int solve (int i, int j)
{

    int t1,t2,total;
    if( i &gt; rownum-1 ) {
        return 0;
    }
    else {
        if (cache[i][j] != 0 &amp;&amp; ( i &lt; 50) &amp;&amp; ( j &lt; 50)) { //for small values use memoization
            return cache[i][j];
        }
        t1 = solve(i+1,j);
        t2 = solve(i+1,j+1);
        total = max(t1,t2) + a[i][j];
        cache[i][j] = total;//store in cache
    }
    return total;
}
int main(int argc, char *argv[])
{
    int tries;
    cin&gt;&gt;tries;
    while(tries--) {
        cin&gt;&gt;rownum;
        int temp = rownum;
        for ( int i = 0 ; i &lt; rownum ; i++) {
            a.push_back(vector1D(rownum,0));//initialize memory
        }
        for ( int j = 0; j &lt; 10; j++) {
            cache.push_back(vector1D(10,0));//initialize cache
        }
        for ( int i = 0; i &lt; rownum; i++) {
            for ( int j = 0 ; j &lt;= i; j++) {
                cin&gt;&gt;a[i][j];
            }
        }
    cout&lt;&lt;solve(0,0)&lt;&lt;endl;//call the solving function
    cache.clear();
    }
    return 0;
}
General Comments.
I hate your use of global variables.
int rownum;
int noOfCalls = 0;
vector2D a;
vector2D cache; // The cache to implement memoization

I suppose it is an attempt at better performance.
The test for j here is redundant:
if (cache[i][j] != 0 &amp;&amp; ( i &lt; 50) &amp;&amp; ( j &lt; 50)) 

If i is smaller than 50 then j can not be greater than 50. If i is greater than 50 then the test will fail and there is no need to test what the value of j is.
Bugs
    for ( int i = 0 ; i &lt; rownum ; i++) {
        a.push_back(vector1D(rownum,0));//initialize memory
    }

As you never clear a the size increases for every puzzle.
This can become quite expensive as a will continuously keep breaking its buffer and have to be re-allocated (copying all those internal arrays).
Speed
If you are solely going for speed then operator&gt;&gt; is about half the speed of scanf as it (operator&gt;&gt;) takes into account a lot of local stuff that is not done with scanf.
Your recursive algorithm is computing some spots multiple times.
// Your Triangle
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15

// Number of times each spot is hit with recursion
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

As you can see some of the spots in the center bottom of the triangle are being hit many many times by recursion when you only want to hit each location once. Thus an iterative solution is probably better.
You are using a 2D array to represent the triangle which requires two de-references (which can be inefficient (but without measuring I am not convinced this is a major issue)). Rather than do that use a 1-D array given the number of rows n you can quickly compute the number of elements in the triangle as n*(n+1)/2 and thus re-size the array in one statement. Element access for a child of m is m+row(m)+0 and m+row(m)+1 (note the calculation of row(m) does not need to be done each time you can keep track of this as you increment m).