CODEWITHSUNDEEP
algorithmgraphtreepermutationdynamic-programming
Arun Kumar
Arun Kumar

Reputation: 694

Count the number of possible ways of crossing hurdles to reach a destination?

I have a problem with starting location, followed by a number of hurdles at different distances, and then an end location. The maximum jump size to cross the hurdles is 20. My goal is to reach the end location by jumping across the hurdles with the maximum jump size.

Example:

{0, 15, 20, 25, 29, 31, ......, 45}

In this above array, '0' is the starting location; '45' is the end location; and everything else in the middle are way-points at different distances (15, 20, 25, 29, 31, etc.). There are hurdles between successive way-points. Assume that the array is always sorted in the ascending order from the start to the end location. How can I calculate all possible ways of reaching the end location with different permutations of jumps across the hurdles (each jump being within the maximum jump size) ?

Upvotes: 0

Views: 207

Answers (1)

Prune
Prune

Reputation: 77847

This is solvable with either dynamic programming or DFS (depth, not breadth), depending on how you look at the problem. Either way, you're going to memoize the solution from each way-point to the end. You can work from either end; the problem is entirely reversible. Let's consider the sequence {0, 8, 9, 15, 20} and a jump size of 10.

Starting from 0, you can reach nodes 8 and 9.  You'll recur on each of those.
From 8, you can reach 9 and 15; you'll recur on each.
From 9, you can reach only 15.
From 15, you can reach only 20.

Climbing back up your recurrence tree:

There's 1 way to get to the end from 20 (vapid result), so f(20) = 1
From 15, there's one way to reach the end: through 20, so f(15) = 1
From 9, there's one way to reach the end: through 15, so f(9) = 1
From 8, you have two choices: 9 and 15.  f(8) = f(9) + f(15) = 1 + 1 = 2
From 0, you have two choices: 8 and 9.  f(0) = f(8) + f(9) = 2 + 1 = 3

See how that works? The dynamic programming part is working backward: once you've computed f(9) the first time (in computing f(8)), you remember the result, and don't repeat the computation when you compute f(0).

Upvotes: 1

Related Questions