I am trying a simple recursive approach here. From each dimension, I am checking whether or next I can move forward to next dimension. If so I am moving there and return back to the present position to check whether backward movement is possible or not.
Problems I am facing :
If I comment out one recursion (either), the answer becomes zero.
If both recursions are present then it is infinite loop
In first if statement if I remove arr[i]-- or in second if I remove arr[i]++, I am getting wrong answer (but no infinite loop or zero as the answer).
Where have I gone wrong? Please help
p.s. Is there any other approach for this problem?
I guess your “infinite loop” isn’t infinite but rather 2^N for a somewhat big N.
The reason is: You’re not using DP yet. Enumerating all possibilities is far to slow. Check waht your state during the recursion is and memoize it (just do it for 1d - high dimensions wont run in that way anyway).
To get to higher dimensions think about how you can construct higher dimensional paths out of the 1d-version.
how can I store the states? I mean maximum dimension is 10 and each dimension can have value upto 100. So I will require a 100^10 element array to store each state. Correct me if I am wrong.
And can you elaborate that 2^n part? n is 10 at max. So 2^10 = 1024 isn’t too large I think
I’m sorry, I didn’t use matching notation. I meant 2^m, m being the length of the path. m is the recursion depth of your algorithm, splitting (except on the edges of the square) 2 times per call yields 2^m for the 1-n-case.
Youre completely right with your concern about storage space for high n, but it doesn’t help not to store, your algorithm as is will be too slow by far.
Use your algorithm with memo for n=1, and think about how to compute the value for n>1 out of solving n one dimensional problems.