CareerCup

start at index 1,
now let us say at index 1, integer is k.
for all x= 1 to x<=k, check a[x] (choose the one with greatest value...similar step at that index)
Greedy algo.

It's a dynamic programming problem

Let Sel(n) be the solution which in the number of selections to be made to reach the end of the array of size n.

then Sel(n) = Min(Sel(k))+ 1 <--( for all k < n such that a[k] >= (n-k))-->

assume
jump(c,i) gives no of jumps required to reach index i.

intially c i.e. cost of jumping to ith index can not be grater than i.
assume n as length of given array.

Idea is to corelate problem with knapsack problem.

algo would be:

jump(c,i)
{
if(i>=n)
//we have traversed complete array
return 0;

if(a[i]==0)
i=i+1;

else
return min(jump(c,i+1), 1 + jump(c-1,i+1));

}

any comments?

initial call :
jump(<length of array>,0);

I dont think it is dynamic programming... or may b i didnt get the problem right...

Say we are given a sequence 1 | 3 | 5 | 2 | 3 | 2 | 6 | 7 | 6 | 8 | 9
True we need to compute the minimum jumps at each position. So say we are at 3. The window for 3 is 5 ,2 , 3 . Now we need to chose one from this window. If we select the one that gives a window of max range that is the hop from 3.So in this case 5 and 3 give a window which ranges till 7. So we choose 5. Now we know that 2 & 3 gave a window which was less than what 5 gave. Thus we need not re-compute the value for 2 & 3. Unless the last and only value in 5's window is zero we wont be stuck.But this would be the case for all elements in 3's window if they give a window less than 5. Thus we can choose a value from 5's window which just includes new values( that is does not contain elements from 3's window).

Let me know if this approach is wrong. The only reason I dont think its dynamic programming is we dont need to recompute values and hence need not store them.

This is the brute force attack, i can think

i = 1
while i < n:
  j = i
  for k in range(i, i+a[i]):
    if a[i] - (k-i) > a[i]:
      j = k
  i = j
  print i

DP solution to find the number of jumps. not the sequence though.

jump[n]=1 if A[n] > 0
=infinite otherwise
for i = n-1 downto 1
jump[i] = 1 , if n-A[i]+1 > n
= infinite , if A[i] <= 0
= 1+min(jump[j]) for all j = i+1 to i+A[i] and j < n otherwise

jump[n]=1 if A[n] > 0
       =infinite otherwise
for i = n-1 downto 1
jump[i] = 1 , if n-A[i]+1 > n
        = infinite , if A[i] <= 0
        =  1+min(jump[j])   for all j = i+1 to i+A[i] and j < n otherwise

You can think of array size as number of nodes in a graph
For every node a[i] you can reach i+a[i] nodes from it with weight 1 for each node
You can see this nodes as in topological order
find the shortest path
suppose array 1,3,5,2,3
Node 1 can go to Node 2 with weight 1
Node 2 can go to Node 3,4,5 with weight 1
similarly you can do for all and see the
shortest path is from 1->2->5(this are node number)

int numberOfHops(int[] arr) {
		int[] dpArray = new int[arr.length];
		int i = 0;
		for(; i<dpArray.length - 1; i++){
			dpArray[i] = Integer.MAX_VALUE;
		}
		for(i--; i>=0; i--) {
			int maxHops = Math.min(dpArray.length - i -1, arr[i]);
			for(int j=1; j <= maxHops; j ++) {
				if(dpArray[i+j] == Integer.MAX_VALUE) continue;
				dpArray[i] = Math.min(dpArray[i], dpArray[i+j] + 1);
			}
		}
		return dpArray[0];
	}

function [k, p] = minJumps(a)

n = numel(a);

K = zeros(1,n); % Count jumps to get at i
P = zeros(1,n); % Predecessor of element at i

for i=2:n
    K(i) = n+1;
    for j=1:i-1
        if(a(j) >= i-j)
            if(K(i) > 1 + K(j))
                K(i) = 1 + K(j); % Update minimum count
                P(i) = j;        % Update predecessor
            end
        end
    end
end

k = K(n);
p = [];

i=n;
% Select only predecessor chain to the last element
while(i>0)
    p = [i, p];
    i = P(i);
end
end

This is a MATLAB implementation using DP. We keep an array K of counted jumps to each element, and also an array P of predecessor indexes. At the end, we walk backward P and pick up only the values needed to traverse the array to the last element. Solutions are not unique, but an optimal solution is always returned.

Thanks!

If you just need to find the least count...it could be done this way

int steps ( int * s ,int sum)
{
int k,num= *s;
sum= sum- num;

if( sum <=0 )
return 1;

for (k=1; k<=num && sum>0; k++)
return(1+steps (&(*(s+k)), sum));
}

int main()
{
int step[]= {1,3,8,9,2,6,7,6,8,9};
len=sizeof(step)/sizeof(int);
printf( " min number of steps taken is %d \n" , steps(step,len));
}

DP in Python:

def jumpy(a):
    n = len(a)
    dps = (n-1)*[None] + [(0,None)]

    def recurse(root):
        root_dps = None
        for next in range(root+1, min(a[root]+root+1,n) ):
            if not dps[next]:
                recurse(next)
            next_njump = dps[next][0] + 1
            if (root_dps is None) or (next_njump < root_dps[0]):
                root_dps = (next_njump, next)
        dps[root] = root_dps

    recurse(0)
    print('Minimum path indices = ', end='')
    i = 0
    while i != n-1:
        print(str(i) + '->', end='')
        i = dps[i][1]
    print(str(n-1))
    print('Minimum number of jumps = ' + str(dps[0][0]))

jumpy([1,3,5,8,9,2,6,7,6,8,9])

Output is:
Minimum path indices = 0->1->3->10
Minimum number of jumps = 3

Sorry ... code formatting went wrong ... reposting:

def jumpy(a):
    n = len(a)
    dps = (n-1)*[None] + [(0,None)]
    def recurse(root):
        root_dps = None
        for next in range(root+1, min(a[root]+root+1,n) ):
            if not dps[next]:
                recurse(next)
            next_njump = dps[next][0] + 1
            if (root_dps is None) or (next_njump < root_dps[0]):
                root_dps = (next_njump, next)
        dps[root] = root_dps
    recurse(0)
    print('Minimum path = ', end='')
    i = 0
    while i != n-1:
        print(str(i) + '->', end='')
        i = dps[i][1]
    print(str(n-1))
    print('Minimum number of jumps = ' + str(dps[0][0]))

jumpy([1,3,5,8,9,2,6,7,6,8,9])

I agree with the "graph" solution...only one word of caution....do not draw an edge from a node to a target node if the value of the array for the target node is "0"....also no outcoming edges from a node which has value "0"...in the array....

So many posts. reading all of them make me sleepy.

a brute force method.

approach:

for the element on the index, iterate from i:1->element and go to the i(th) location and repeat the step again . using this thought in recursion will extend as :

void jump ( int a[], int length, int currentIndex, int jumps, int *minJumps)
{
   if(jumps > =  length)
   {
      *minJumps=(*minJumps > jumps ) ? jumps : *minJumps;
      return; 
   }

   int value=a[currentIndex];
   
   for(i=1 ; i<= value; i++)
   {
      jump(a,length,currentIndex+i,jumps+i,minJumps);
   }
}

public static void main(String args[])
	{
		 LinkedList<Integer> steps = new LinkedList<Integer>();
		int a[] ={1 ,3 ,5, 8, 9, 2, 6, 7, 6, 8, 9};
		calculate(a,0,0,steps);
	}
	private static void calculate(int[] a, int start, int step,LinkedList<Integer> steps) {
		if(start>=a.length)
			return;
		if(a[start]<=0)
			return;
		if(start==a.length-1){
		    System.out.println(steps);
			return;
		}
		for(int i=1;i<=a[start];i++)
		{
			steps.addLast(start);
			calculate(a,start+i, step+1,steps);
			steps.removeLast();
		}
	
	}