Recursion based problem

Question

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.

-------------------------

|0 | 3 | 80 | 6 | 59 | 10|

-------------------------

The object of the game is to move from the first column to the last column in the total lowest cost. The number in each column represents the cost to enter that column. 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. 

Write a recursive solution to this problem that calculates the cheapest possible cost and outputs this value, for an arbitrarily large game board represented as an array. Your program does not 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

Answer 1

#include <stdio.h>

#define MAX_INDEX (5)

int smallestSum=32767;

void jumpit ( int * A, int iIndexPos,int sum)

{

printf(" jump it : iIndexPos = %d : sum = %d \n",iIndexPos,sum);

if (iIndexPos<MAX_INDEX)

{

//can always jump one position from current index

iIndexPos++;

sum += A[iIndexPos];

jumpit(A,iIndexPos,sum);

// can jump one OR two positions from current index

if ((MAX_INDEX-iIndexPos)>=2)

{

iIndexPos +=2;

sum += A[iIndexPos];

jumpit(A,iIndexPos,sum);

}

}

if (sum < smallestSum)

{

printf(" updating smallestSum to %d \n",sum);

smallestSum = sum;

}

}

int main()

{

int a[6]={0,3,80,6,59,10};

jumpit(a,0,0);

printf(" smallest sum is %d ",smallestSum+a[MAX_INDEX]);

}