Finding the length of the number of paths in a matrix I found this problem from leetcode.com. We are asked to find the longest increasing path in a matrix. I finally came up with a recursion to achieve this but I found that when I increase the rows and columns to a large size then my program takes a long time to run.

I am wondering if there is any way I can optimize my code for speed, or perhaps if there is a better approach I can consider. I know that some have used dynamic programming and depth first search to achieve good speeds but to be honest I haven't really gotten there yet in my programming level.

#include &lt;algorithm&gt;
#include &lt;cmath&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;random&gt;

using namespace std;


#define MATRIX_SIZE 1000

void printPath() {

}

int check(int i, int j, vector&lt;vector&lt;int&gt; &gt; matrix, vector&lt;vector&lt;int&gt; &gt; length) {
    if (length[i][j] == -1) {
        int currentValue = matrix[i][j];

        int len = 0;
        if ((i &gt; 0) &amp;&amp; (matrix[i-1][j] &gt; currentValue)) { // check up
            len = max(len, check(i-1, j, matrix, length));
        }
        if ((i + 1 &lt; matrix.size()) &amp;&amp; (matrix[i+1][j] &gt; currentValue)) { // check left
            len = max(len, check(i+1, j, matrix, length));
        }
        if ((j &gt; 0) &amp;&amp; (matrix[i][j-1] &gt; currentValue)) { // check down
            len = max(len, check(i, j-1, matrix, length));
        }
        if ((j+1 &lt; matrix[i].size()) &amp;&amp; (matrix[i][j+1] &gt; currentValue)) { // check right
            len = max(len, check(i, j+1, matrix, length));
        }
        length[i][j] = len + 1; // Include current cell
    }
    return length[i][j];
}

int longestPath(vector&lt;vector&lt;int&gt; &gt; matrix) {
    int n = matrix[0].size();
    int m = matrix.size();
    vector&lt;vector&lt;int&gt; &gt; length(m, vector&lt;int&gt;(n,-1));

    int len = 0;
    for (int i = 0; i &lt; m; i++) {
        for (int j = 0; j &lt; n; j++) {
            len = max(len, check(i, j, matrix, length));
        }
    }
    return len;
}


int main() {
    // Specify the number of rows and columns of the matrix
    int n = MATRIX_SIZE;
    int m = MATRIX_SIZE;

    // Declare random number generator
    mt19937 gen(10);
    uniform_int_distribution&lt;&gt; dis(1, 1000000);

    // Fill matrix
    vector&lt;vector&lt;int&gt; &gt; matrix;
    for(int i = 0; i &lt; m; i++) {
            vector&lt;int&gt; row;
        for(int j = 0; j &lt; n; j++) {
            row.push_back(0);
        }
        matrix.push_back(row);
    }

    // Apply random number generator to create matrix
    for(int i = 0; i &lt; m; i++) {
        for(int j = 0; j &lt; n; j++) {
            matrix[i][j] = dis(gen);
        }
    }

    // Print matrix to see contents
//  for(int i = 0; i &lt; m; i++) {
//      for(int j = 0; j &lt; n; j++) {
//          cout &lt;&lt; matrix[i][j] &lt;&lt; " ";
//      }
//      cout &lt;&lt; endl;
//  }
//  cout &lt;&lt; endl;

    int result = longestPath(matrix);
    cout &lt;&lt; result &lt;&lt; endl;





}
Don't do using namespace std;.




void printPath() {

}



This empty function does not do anything, so better remove it to make the code cleaner.




// Print matrix to see contents
//  for(int i = 0; i &lt; m; i++) {
//      for(int j = 0; j &lt; n; j++) {
//          cout &lt;&lt; matrix[i][j] &lt;&lt; " ";
//      }
//      cout &lt;&lt; endl;
//  }
//  cout &lt;&lt; endl;



Commented code clutters the code and can confuse the reader. "Is it still needed? Then why is it commented out? If not, why is it still there?". Apparently it is not used anymore, and it also tells the reader nothing about the code, so better delete it.




// Specify the number of rows and columns of the matrix
int n = MATRIX_SIZE;
int m = MATRIX_SIZE;



The comment here should not be needed, because the code explains itself. Maybe it would be even more explicit if you named the variables rows and columns. If n and m do not change, and you have MATRIX_SIZE defined anyways, you could just use MATRIX_SIZE instead of the variables.




// Declare random number generator
mt19937 gen(10);
uniform_int_distribution&lt;&gt; dis(1, 1000000);



A more explicit variable name would make this comment obsolete. Less comments means less to read and makes the code easier to understand. Comments should tell the reader why the code does something, but the code should explain what it does itself. rng would be short and is a well known acronym for random number generator.