//

// Solution45.cpp

// Algorithm

//

// Created by Pancf on 2021/1/3.

//

#include "Solution45.hpp"

int Solution45::jump(std::vector<int>& nums)

{

int size = (int)nums.size();

if (size == 1) return 0;

std::vector<int> steps(size, 0); //steps[i]表示到达i所需要的最少步数

int maxReachableIdx = 0;

for (int i = 0; i <= maxReachableIdx && i < size; ++i) {

// 从当前位置i能到达更远位置或者能到达终点时，就要尝试更新steps

if (maxReachableIdx < nums[i] + i || nums[i] + i >= size - 1) {

maxReachableIdx = nums[i] + i;

for (int j = i + 1; j <= maxReachableIdx && j < size; ++j) {

if (steps[j] == 0) {

steps[j] = steps[i] + 1;

} else {

steps[j] = std::min(steps[i] + 1, steps[j]);

}

}

}

}

return steps[size - 1];

// if (size == 1) return 0;

// int largestLadderLen = nums[0]; // ‘梯子’最远能到达的坐标

// int stepsLeftOnLadder = nums[0]; // 当前‘梯子’还剩几步可以使用

// int steps = 1;

// for (int i = 1; i < size; ++i) {

// stepsLeftOnLadder--; // 每走一步，当前‘梯子’可用步数减一

// int newLadder = i + nums[i];

// largestLadderLen = std::max(largestLadderLen, newLadder); // 更新‘梯子’最远能到达的坐标

// if (stepsLeftOnLadder == 0) { // 把当前‘梯子’可用步数耗尽后才使用新的‘梯子’，此时新‘梯子’可能已经‘走了’几步了

// steps++;

// stepsLeftOnLadder = largestLadderLen - i;

// }

// }

// return steps;

}