CODEWITHSUNDEEP
c++arraysalgorithmdynamic-programming
Alin
Alin

Reputation: 159

Max number ways to jump to the last element

I had a question from a contest and would like to know the solution.

Question is about finding max number of unique ways to jump to last element. I am thinking about a solution with dynamic programming but couldnt figure it out.

You can jump max 3 steps in any position. Number of steps will be given as n, and our program should calculate Max number of jumps to reach n+1 position.

For example: n=4, max number of jumps to n+1 position should be 7

Jump1: 1 2 1    
Jump2: 1 1 2    
Jump3: 2 1 1    
Jump4: 1 3    
Jump5: 3 1    
Jump6: 2 2    
Jump7: 1 1 1 1

Thank you

Upvotes: 1

Views: 303

Answers (3)

rici
rici

Reputation: 241911

The longest journey, says the proverb, starts with a single step.

In this case, there are three possible first steps in the journey to the end: a hop of 1, 2 or 3 spots. In each case, the journey will continue from a closer point, either 1, 2 or 3 steps closer to the end. So if we know the number of possible paths from the closer points, we can simply add them up:

paths(n) = paths(n-1)   // First hop was one,   n-1 elements left
         + paths(n-2)   // First hop was two,   n-2 elements left
         + paths(n-3)   // First hop was three, n-3 elements left.

The similarity to the Fibonacci recursion is not coincidental. This sequence is often called the "Tribonacci sequence", and you can easily look that up in the usual places (mathworld, wikipedia, oeis, etc.) to find a variety of computation techniques, including the one below.

Clearly, you can compute the Tribonacci function in O(n) by starting at the end and working backwards (defining f(0) = 1, f(-1) = 0, f(-2) = 0 to provide a starting position.) But it's easy to do better than that, using the same technique that can be used to compute Fibonacci numbers in O(log n) operations.

Here's the Fibonacci algorithm. We start with the observation that the matrix product:

          | 1  1 |
[ a b ] x |      |  = [ a+b a ]
          | 1  0 |

Let's use F(n) for the nth Fibonacci number, and call matrix of 1s and 0s above MF. We can see that

[ F(n) F(n-1) ] = [ 1 0 ] × MF × MF × … × MF
                              n products

But since matrix multiplication is associative, we can rewrite that as:

[ F(n) F(n-1) ] = [ 1 0 ] × MFn

Again, since matrix multiplication is associative, we can compute MFn in O(log N) steps. For example, we could use the recursion:

    = Mn/2 × Mn/2 if n is even
Mn
    = M × M(n-1)/2 × M(n-1)/2 if n is odd

Similarly, for the Tribonacci numbers T(n), we can define the matrix MT:

     | 1 1 0 |
MT = | 1 0 1 |
     | 1 0 0 |

and by the same logic as above:

[ T(n) T(n-1) T(n-2) ] = [ 1 0 0 ] × MTn

Upvotes: 3

Brad Wells
Brad Wells

Reputation: 429

The important function is going to be (number_of_elements)!/product((number_repeated_characters)!)

For instance, if you know 2211 is one of your paths, then 4!/2!*2! = 6 so there are 6 path combinations for 2 "2"s and 2 "1"s.

Since you're only going up to a maximum of 3 steps, it's really not too bad once you know that formula. Really you're just looking for the combinations of 2s and 3s that can replace the 1s in your input. I suggest starting with 1 3 and then going through each 2 that fills in the remainder. Then repeat for 2 3s and so on. If you precompute and save all the factorials, it should run very fast, although I'm sure there are additional optimizations.

Upvotes: 0

Mohit Jain
Mohit Jain

Reputation: 30489

Do you know number of ways for n = 0, n = 1 and n = 2?

For any larger value N, number of ways = number of ways for N - 1 + number of ways for N - 2 + number of ways for N - 3

You should not calculate the number of ways for given n more than 1 time. (Remember it in a dp array)

Upvotes: 2

Related Questions