Sunday, April 5, 2015

Robot Steps

.Problem:
A robot can take 2, 3 or 5 steps at a time. Given the difference (total number of steps) between source and destination, find the number of ways the robot can reach from source to destination.

Sample Input:
1
2
3
4
5
6
7
8
9

Sample Output:
0
1 
1
1
3
2
5
6
8

Solution:
The solution to these problems can be generalized in the following manner:
If a robot can take a, b, c, ... steps to move from one position to another, then the total number of ways to traverse a particular number of steps n is:
A[n] = A[n-a] + A[n-b] + A[n-c] + ...

So in this case, the recurrence formula is:
A[n] = A[n-2] + A[n-3] + A[n-5]