Problem Statement (https://www.geeksforgeeks.org/count-number-of-ways-to-cover-a-distance/):
Given a distance ‘dist, count total number of ways to cover the distance with 1, 2 and 3 steps.
Examples :
Input: n = 3
Output: 4
Below are the four ways
1 step + 1 step + 1 step
1 step + 2 step
2 step + 1 step
3 step
Input: n = 4
Output: 7
Explanation:
If we know the number of ways to reach the distances k-3, k-2, k-1, then the kth distance is just 3, 2 and 1 hops away respectively. So dp[k] = dp[k-3] + dp[k-2] + dp[k-1]
Code:
Given a distance ‘dist, count total number of ways to cover the distance with 1, 2 and 3 steps.
Examples :
Input: n = 3
Output: 4
Below are the four ways
1 step + 1 step + 1 step
1 step + 2 step
2 step + 1 step
3 step
Input: n = 4
Output: 7
Explanation:
If we know the number of ways to reach the distances k-3, k-2, k-1, then the kth distance is just 3, 2 and 1 hops away respectively. So dp[k] = dp[k-3] + dp[k-2] + dp[k-1]
Code:
No comments:
Post a Comment