Mark has $N$ days. Initially he is at position $(h1,0)$ on the X-axis. On each day he can go to the co-ordinates $(x+a,0)$ or $(x+b,0)$ or $(x+c,0) .$ where $(x,0)$ is his current position.
He can select any one of the choice he wants. Each day he can go to (+a , +b or +c) from his current position. At the N-th day, he has to reach the position $(h2,0)$. Count the number of ways in which Mark can reach $(h2,0)$ in N days.
Values of $N,h1,h2,a,b,c$ are large(co-ordinates and values of a,b,c can be negative as well, in some cases a=b or b=c or c=a or a=b=c)
My approach is:- At each day, I store the positions which he can reach on that particular day with the count(number of ways) to reach that position. I am using a map to do this. And this approach is not efficient.
Can somebody share a much more efficient approach ?
Can we derive some formula for this problem or a recurrence relation which can solve it efficiently ?
Answer : -7(number of ways)
Format:-(Choice on 1st day+Choice on 2nd day+Choice on 3rd day)