数组跳

#include <iostream>
#include <vector>

using namespace std;

//数组跳问题，给一个非负整数数组（数组中的每个元素代表在该位置可以跳跃的最大长度），使用最少的跳跃次数到数组的最后一个人位置。

int MaxCount(vector<int> arr)
{
    if (arr.size() == 0 || arr.size() == 1) //如果数组个数为0或者为1，则不需要跳
    {
        return 0;
    }

    if (arr[0] > arr.size())                //如果第一个数大于数组个数，则一步直接可以到达
    {
        return 1;
    }

    int cur = 0, pre = 0;                   //当前能到达的最远位置和之前能到达的最远位置
    int jums = 0;

    int i = 0;                              //当前遍历的数组下标

    while (cur < arr.size() - 1)            //如果当前能到达最后一个位置，则结束循环
    {
        jums++;

        pre = cur;                          //更新之前所能到达的最远位置
        for (; i <= pre; i++)               //遍历在上次可以跳到的范围内，当前能跳到的最远的范围
        {
            cur = max(cur, i + arr[i]);     //更新当前能够跳的最远的位置
        }

        if (cur == pre)                     //如果当前能到达的位置和上次没有变化，则到不了最后一个位置
            return -1;
    }

    return jums;

}
int main(int argc, char** argv)
{
    //vector<int> arr = { 2,3,1,1,4 };
    vector<int> arr = { 3,2,1,0,4 };

    int jumps = MaxCount(arr);
    cout << jumps << endl;

    return 0;
}