We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
In the abstract, the problem is to find the number of paths from (0,0) to any point (i,j) in a grid whose nodes are pairs of non-negative integers. Looking at it this way, it's pretty easy to see that Npath(i,j) = Npath(i-1,j) + Npath(i, j-1). Picture Pascal's Triangle.
So, the solution is the number of combinations of n + m - 2 things taken n - 1 at a time -- or m - 1 at a time, it doesn't matter.
The problem I'm having is that my solution is timing out, and I don't know a faster way to compute the answer.
Matrix Tracing
You are viewing a single comment's thread. Return to all comments →
In the abstract, the problem is to find the number of paths from (0,0) to any point (i,j) in a grid whose nodes are pairs of non-negative integers. Looking at it this way, it's pretty easy to see that Npath(i,j) = Npath(i-1,j) + Npath(i, j-1). Picture Pascal's Triangle. So, the solution is the number of combinations of n + m - 2 things taken n - 1 at a time -- or m - 1 at a time, it doesn't matter. The problem I'm having is that my solution is timing out, and I don't know a faster way to compute the answer.