1. Member
Join Date
Apr 2008
Posts
42
Rep Power
0

Hey guys ... This is basically what im trying to do .

The game of “Jump It” consists of a board with n positive integers in a row except for the first column, which always contains zero. These numbers represent the cost to enter each column. Here is a sample game board where n is 6:

The object of the game is to move from the first column to the last column in the lowest total cost. The number in each column represents the cost to enter that column. You always start the game in the first column and have two types of moves. You can either move to the adjacent column or jump over the adjacent column to land two columns over. The cost of a game is the sum of the costs of the visited columns.
In the board shown above, there are several ways to get to the end. Starting in the first column, our cost so far is 0. We could jump to 80, then jump to 57, then move to 10 for a total cost of 80+57+10 = 147. However, a cheaper path would be to move to 3, jump to 6, then jump to 10, for a total cost of 3+6+10 = 19.

Write a recursive solution to this problem that computes the cheapest cost of the game and outputs this value for an arbitrarily large game board represented as an array. Your program doesn’t have to output the actual sequence of jumps, only the cheapest cost of this sequence. After making sure that your solution works on small arrays, test your solution on boards of larger and larger values of n to get a feel for how efficient and scalable your solution is.

and here is where I got in the recursive phase

public static int Calc(int[] a,int i){
if(i==a.length-1){
return a[i];
}

else{
//System.out.print(Math.min(a[i],a[i+1])+"+");
return Math.min(a[i],a[i+1])+Calc(a,i+1);

}

I just dont know what im doing wrong !!!?? it keeps adding the same element

2. ## What board...

In the board shown above, ...
What board? Don't see any board.

CJSL

3. Member
Join Date
Apr 2008
Posts
42
Rep Power
0
Sorry ,, it didnt get copied :P .. the board is just an array of 6 blocks with the number zero as the first number and the other numbers are at random. Anyway, I can only jump one or two blocks and I have to find the smallest values and add them .. for example .. 0 , 1 ,4 ,2 6 ,76 :
I can only move either from 0 to 1 or from 0 to 4 and then lets say from 1 to 4 or 1 to 2.. until i reach the last number and add it. in this case i am supposed to add 1+2+76 because i need to get the least sum as possible. << this is the simplest way i can explain it :(

4. Member
Join Date
Apr 2008
Posts
42
Rep Power
0
The program HAS to find the minimum numbers to add with he final number. So there is supposed to be only one way.

0 1 5 3 6 8 << this is the board. The program HAS to calculate it this way 1+3+8 .. because it is less than 1+3+6+8 The rules are that the program can only jump one block or 2 blocks. so it can go to 1 or 5 when we start from 0. but since 1 is less than 5 it will go to 1. Then when we r at 1 it can either go to 5 or 3, but since 3 is less than 5 it will add 1+3 and now we are at block containing the number 3. since it can move to 6 or 8 but because 8 is the last block then it will add 1+3+8 and we skip 6. even thought 6 is less than 8 because we want the minimum sum. so 1+3+8 is less than 1+3+6+8 did u get it now :) ?

5. Java Code:
```public static int Calc(int[] a,int i){
if(i==a.length-1){
return a[i];
}```
This will return the last array element when you reach the end of the array.
What you want is to add the cost (last element) to the ongoing/total cost and return the totalCost.
To do this you will need to pass the totalCost along as a method parameter.

6. Member
Join Date
Apr 2008
Posts
42
Rep Power
0
Thanx, but I already did that, but I couldnt figure out how to add the cheapest cost.

7. Java Code:
```int getCost(int[] array, int index, int totalCost) {
if index == last array index

if we can advance one more index in the array
cost = array element at index +1

if we can advance two more indices in the array
next cost = array element at index +2
// Since we're here we have two options to
// choose from so:
pick the lower cost
and the index of the lower cost

print lower cost and its index in the array

// In recursion you add values on the fly:
return getCost(array, new index, totalCost + new cost);
}```

8. Member
Join Date
Apr 2008
Posts
42
Rep Power
0

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•