Thursday, January 17, 2019

Ways to cover distance, DP

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:



No comments:

Post a Comment