Dynamic Programming - Jumping jacks

Question

Can some one help in solving the below problem using DP technique.

No need of code. Idea should be enough.

Marvel is coming up with a new superhero named Jumping Jack. The co-creator of this superhero is a mathematician, and he adds a mathematical touch to the character's powers.

So, one of Jumping Jack's most prominent powers is jumping distances. But, this superpower comes with certain restrictions.

Jumping Jack can only jump —

1. To the number that is one kilometre lesser than the current distance. For example, if he is 12 km away from the destination, he won't be able to jump directly to it since he can only jump to a location 11 km away.
2. To a distance that is half the current distance. For example, if Jumping Jack is 12 km away from the destination, again, he won't be able to jump directly to it since he can only jump to a location 6 km away.
3. To a distance that is ⅓rd the current distance. For example, if Jumping Jack is 12 km away from the destination, once more, he won't be able to jump directly to it since he can only jump to a location 4 km away.

So, you need to help the superhero develop an algorithm to reach the destination in the minimum number of steps. The destination is defined as the place where the distance becomes 1. Jumping Jack should cover the last 1 km running! Also, he can only jump to a destination that is an integer distance away from the main destination. For example, if he is at 10 km, by jumping 1/3rd the distance, he cannot reach 10/3rd the distance. He has to either jump to 5 or 9.

So, you have to find the minimum number of jumps required to reach a destination. For instance, if the destination is 10 km away, there are two ways to reach it: 10 -> 5 -> 4 -> 2 -> 1 (four jumps) 10 -> 9 -> 3 -> 1 (three jumps) The minimum of these is three, so the superhero takes a minimum of three jumps to reach the point.

Answer 1

You should keep the following 2 points in mind for solving all the Dynamic programming problems:

• Optimal Substructure (to find the minimum number of jumps)
• Overlapping subproblems (If you encounter the same subproblem again, don't solve it, rather used the already computed result - yes, you'll have to store the computed result of sub-problems for future reference)

Always try to make a recursive solution to the problem at hand (now don't directly go ahead and look at the recursive solution, rather first try it yourself):

calCulateMinJumps(int currentDistance) {
    if(currentDistance == 1) {
        // return jumps - you don't need to recurse here
    } else {
        // find at what all places you can jump
        jumps1 = calculateMinJumps(n-1) + 1
        if(currentDistance % 2 == 0)
            jumps2 = calculateMinJumps(n/2) + 1
        if(currentDistance % 3 == 0)
            jumps3 = calculateMinJumps(n/3) + 1
        return minimum(jumps1, jumps2, jumps3) // takes jump2 and jump3 only if they are valid
    }
}

Now you know that we have devised a recursive solution. The next step is to go and store the solution in an array so that you can use it in future and avoid re-computation. You can simply take a 1-D integer array and keep on storing it.

Keep in mind that if you go by top-down approach - it will be called memoization, and if you go by bottom-up approach - it will be called Dynamic programming. Have a look at this to see the exact difference between the two approaches.

Once you have a recursive solution in your mind, you can now think of constructing a bottom-up solution, or a top-down solution.

In Bottom-up solution strategy - you fill out the base cases first (Jumping Jack should cover the last 1 km running!) and then build upon it to reach to the final required solution.

Now, I'm not giving you the complete strategy, as it will be a task for you to carry out. And you will indeed find the solution. :) - As requested by you - Idea should be enough.

Answer 2

Firstly, think about this coin changing problem may help you understand yours, which are much the same: Coin change - DP

Secondly, usually if you know that your problem has a DP solution, you can do 4 steps to solve it. Of cause you can ommit one or all of the first 3 steps.

1. Find a backtrack solution.(omitted here)

2. Find the recursion formula for your problem, based on the backtrack solution. (describe later)

3. Write a recursion code based on the recursion formula.(Omitted)

4. Write a iterating code based on step 3.(Omitted)

Finaly, for your question, the formula is not hard to figure out:

minStepFor(distance_N)=Math.min(minStepFor(distance_N-1)+1),
                                minStepFor(distance_N/2)+1, 
                                minStepFor(distance_N/3)+1)

Just imagine jack is standing at the distance N point, and he has at most three options for his first go: go to N-1 point, or N/2 point, or N/3 point(if N/2 or N/3 is not integer, his choice will be reduced).

For each of his choice, the minimum steps is minStepFor(left distance)+1, since he has made 1 move, and surely he will try to make a minimum steps in his left moving. And the left distance for each choice is distance_N-1,distance_N/2 and distance_N/3.

So that's the way to understand the formula. With it it is not hard to write a recursion solution.

Answer 3

Consider f[1]=0 as the number of jumps required when JumpingJack is 1km away is none. Using this base value solve F[2]...f[n] in below manner

        for(int i=2; i<=n; i++) {
            if(i%2==0 && i%3==0) {
                f[i] = Math.min(Math.min(f[i-1]+1, f[i/2]+1), f[i/3] + 1);
            }
            if(i%2==0) {
                f[i] = Math.min(f[i-1]+1, f[i/2]+1);
            }else if(i%3==0) {
                f[i] = Math.min(f[i-1]+1, f[i/3] + 1);
            }else{
                f[i] = f[i-1]+1;
            }
        }
        return f[n];

You don't need to recursively solve the subproblem more than once!