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 57 10
The object of the game is to move from the first column to the last column
with 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 lowest 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 lowest 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 the scalability and
efficiency of your solution.
Answer
#include <iostream>
using namespace std;
#define min(a,b) (a>b)?b:a
int rec_mincost(int n,int *arr){
if(n==1) return(arr[0]);
if(n==2) return(arr[0]+arr[1]);
return(min(rec_mincost(n-1,arr)+arr[n-1],rec_mincost(n-2,arr)+arr[n-1]));
}
int main() {
int N; cin>>N;
int arr[N];
for(int i=0;i<N;i++) cin>>arr[i];
cout<<"min cost : " << rec_mincost(N,arr) ;
return 0;
}
//Optional
//Its Time Complexity is O(2^N) similar to fibonacci recursion
//Better way to solve it is using iteration whose time complexity is O(N)
/*int iter_mincost(int n,int *arr){
arr[n-2]+=arr[n-1];
arr[n-3]+=arr[n-1];
for(int i=n-4;i>=0;i--){
arr[i]+=min(arr[i+1],arr[i+2]);
}
return(arr[0]);
}*/