Let's say we are given matrix of size $N \leq 21 \text{ by } M \leq 21$ each element of the matrix is either $-1$ or number in the interval $[0, 20]$.

We want to count the number of paths that start in some node, visit each number exactly once by moving in only 4 allowed directions: up, down, left and right. We are not allowed do visit the elements where the value in the matrix is $-1$. So, we want to count paths that have exactly length of 21 because there are 21 numbers in the interval $[0, 20]$.

I know that we can solve this with dynamic programming in $O(N \cdot M \cdot (2^{21}))$. But this uses too much memory, is there way to optimize the memory use. I was thinking only about saving only the last row and the current, but if we do such we cannot move in the upper direction, so we wont count some of the solutions.

Is there any way how we can optimize the memory usage.

  • $\begingroup$ N and M are the dimension of the matrix, N is the number of rows and M is the number of columns. $\endgroup$ – someone12321 Jan 4 at 5:51
  • $\begingroup$ 21 is the number of cells that should be visited by the paths, or the length of each path $\endgroup$ – someone12321 Jan 4 at 6:21