Leetcode-Jump Game II

http://oj.leetcode.com/problems/jump-game-ii/

题目描述

  • Given an array of non-negative integers, you are initially positioned at the first index of the array.

  • Each element in the array represents your maximum jump length at that position.

  • Your goal is to reach the last index in the minimum number of jumps.

  • For example: Given array A = [2,3,1,1,4]

  • The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

AC代码

#include <iostream>
#include <cstdio>

using namespace std;

//从第一个数开始,从它的所有可能性中选择可以跳的最远的那个点,跳到那个点,继续上述过程。
int jump(int A[], int n)
{
        int curmax = 0,nextmax = 0, count = 0;
        for(int i = 0; i < n; i++)
    {
        if(i  > curmax)
        {
            curmax = nextmax;
            count++;
        }
        nextmax = nextmax > (A[i] + i) ? nextmax : (A[i] + i);
    }
       return count;
}

int main()
{
        int n;
        cin>>n;
        int A[n];
        for(int i = 0; i < n; i++)
            cin>>A[i];
        cout<<jump(A,n)<<endl;
        return 0;
}