The problem of counting the number of ways to cover a distance can be stated as follows: Given a distance ‘dist‘, count total number of ways to cover the distance with 1, 2, or 3 steps at a time.
For example, if ‘dist = 3‘, the possible ways to cover the distance are:
- {1, 1, 1}
- {1, 2}
- {2, 1}
- {3}The brute force solution for this problem is to use recursion and try all possible combinations of steps. However, this solution has a high time complexity because it generates many overlapping subproblems. Therefore, dynamic programming is a good approach to solve this problem.
We will use a one-dimensional integer array ‘ways‘ of size ‘dist+1‘. The ‘i‘-th element of the array is the number of ways to cover ‘i‘ distance. The base cases are:
- `ways[0] = 1` (there is only one way to cover 0 distance)
- `ways[1] = 1` (there is only one way to cover 1 distance)
- `ways[2] = 2` (there are two ways to cover 2 distance: {1, 1} and {2})The recursive formula for calculating ‘ways[i]‘ is:
ways[i] = ways[i-1] + ways[i-2] + ways[i-3]The reason for this formula is that we can reach distance ‘i‘ by taking a step of size 1, 2, or 3 from distance ‘i-1‘, ‘i-2‘, or ‘i-3‘, respectively. Therefore, the total number of ways to reach ‘i‘ is the sum of the total number of ways to reach ‘i-1‘, ‘i-2‘, and ‘i-3‘.
Here’s the Java code that implements this solution:
public int countWays(int dist) {
int[] ways = new int[dist+1];
ways[0] = 1;
ways[1] = 1;
ways[2] = 2;
for (int i = 3; i <= dist; i++) {
ways[i] = ways[i-1] + ways[i-2] + ways[i-3];
}
return ways[dist];
}For example, if we call ‘countWays(3)‘, the function returns 4 because there are 4 ways to cover a distance of 3.