给定非负整数数组，初始时在数组起始位置放置一机器人，数组的每个元素表示在当前位置机器人一步最大能够跳跃的数目。它的目的是用最少的步数到达数组末端。
例如：
给定数组A=[2,3,1,1,2]，最少跳步数目为2，对应的跳法是2->3->2，数组位置变化为0->1->4。
[2,3,1,1,2,4,1,1,6,1,7]，所需步数为5。
#include<iostream> using namespace std; int jump(int A[],int n){ if(n==1) return 0; int step=0; int i=0,j=0; int k,j2; while(j<n){ step++; j2=j; for(k=i;k<=j;k++){ j2=max(j2,k+A[k]); if(j2>=n-1) return step; } i=j+1; j=j2; if(j<i) return -1; } return step; } int main(){ int A[]={2,3,1,1,2,4,1,1,6,1,7}; int n=sizeof(A)/sizeof(A[0]); cout << jump(A,n) <<endl; return 0; }
原文：http://www.cnblogs.com/AndyJee/p/4985509.html