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.

Example:


Input: [2,3,1,1,4]
Output: 2
Explanation: 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.

Note:

You can assume that you can always reach the last index.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

Greedy algorithms

Starter code: class Solution:
    def jump(self, nums: List[int]) -> int:
        

Solutions:
class Solution:

	def jump(self, nums):
		if len(nums) == 1:
			return 0
		else:
			step = 0
			pos = 0
			while pos != len(nums) - 1:
				bestStep = -1
				bestValue = -1
				for i in range(nums[pos], 0, -1):
					if len(nums) - 1 == pos + i:
						bestStep = i
						break
					if pos + i < len(nums) and nums[pos + i] != 0 and (nums[pos + i] + i > bestValue):
						bestStep = i
						bestValue = nums[pos + i] + i
				print(bestStep)
				pos += bestStep
				step += 1
			return step


class Solution:

	def jump(self, nums):
		res = 0
		n = len(nums)
		(i, j) = (0, 0)
		while j < n - 1:
			print((i, j))
			(ii, jj) = (i, j)
			for k in range(ii, jj + 1):
				j = max(j, min(n - 1, k + nums[k]))
			i = jj + 1
			res += 1
		return res


class Solution:

	def jump(self, nums):
		if not nums:
			return 0
		if len(nums) == 1:
			return 0
		(step, far, maxV) = (0, 0, 0)
		for i in range(len(nums)):
			if i + nums[i] > maxV and i + nums[i] >= len(nums) - 1:
				return step + 1
			maxV = max(maxV, i + nums[i])
			if i == far:
				step += 1
				far = maxV
		return step


class Solution:

	def jump(self, nums):
		p = [0]
		for i in range(len(nums) - 1):
			while i + nums[i] >= len(p) and len(p) < len(nums):
				p.append(p[i] + 1)
		return p[-1]


class Solution:

	def jump(self, nums):
		cur = 0
		ans = 0
		maxstep = 0
		for i in range(0, len(nums) - 1):
			maxstep = max(maxstep, i + nums[i])
			if i == cur:
				ans += 1
				cur = maxstep
		return ans


class Solution:

	def jump(self, nums):
		if len(nums) == 0 or len(nums) == 1:
			return 0
		s = 0
		e = 0
		step = 0
		while e < len(nums) - 1:
			fst = e
			step += 1
			for i in range(s, e + 1):
				if fst < nums[i] + i:
					fst = nums[i] + i
			s = e + 1
			e = fst
		return step


class Solution:

	def jump(self, nums):
		current_step = 0
		last_step = 0
		i = 0
		n_jumps = 0
		while last_step < len(nums) - 1:
			while i <= last_step:
				current_step = max(i + nums[i], current_step)
				i += 1
			last_step = current_step
			n_jumps += 1
		return n_jumps


class Solution:

	def jump(self, nums):
		(n, start, end, step) = (len(nums), 0, 0, 0)
		while end < n - 1:
			step += 1
			maxend = end + 1
			for i in range(start, end + 1):
				if i + nums[i] >= n - 1:
					return step
				maxend = max(maxend, i + nums[i])
			(start, end) = (end + 1, maxend)
		return step


class Solution:

	def jump(self, nums):
		if nums is None or len(nums) <= 1:
			return 0
		start = currEnd = nextEnd = jump = 0
		while currEnd - start + 1 > 0:
			jump += 1
			for i in range(start, currEnd + 1):
				nextEnd = max(nums[i] + i, nextEnd)
				if nextEnd >= len(nums) - 1:
					return jump
			start = currEnd + 1
			currEnd = nextEnd
		return jump


class Solution:

	def jump(self, nums):
		if len(nums) <= 2:
			return len(nums) - 1
		stack = []
		i = len(nums) - 2
		while i >= 0:
			if nums[i] == 1:
				stack.append(i)
			elif nums[i] >= len(nums) - 1 - i:
				if stack:
					stack.clear()
				stack.append(i)
			else:
				j = 0
				while stack and j < len(stack):
					if nums[i] >= stack[j] - i:
						stack = stack[0:j + 1]
						stack.append(i)
						break
					else:
						j += 1
			i -= 1
		return len(stack)


class Solution:

	def jump(self, nums):
		L = len(nums)
		lo = 0
		hi = 0
		jumps = 0
		while hi < L - 1:
			jumps += 1
			nexthi = hi
			for i in range(lo, hi + 1):
				nexthi = max(nexthi, i + nums[i])
				if nexthi >= L - 1:
					return jumps
			(lo, hi) = (hi + 1, nexthi)
		return jumps


class Solution:

	def jump(self, nums):
		if not nums:
			return 0
		dic = {}
		length = len(nums)
		dic[length - 1] = 0
		for j in range(length - 1)[::-1]:
			if nums[j] >= nums[j + 1] + 1 and (not j + 1 == length - 1):
				minstep = dic[j + 1] - 1
				for k in range(max(3, nums[j + 1] + 2), min(length - j, nums[j] + 1)):
					if dic[j + k] < minstep:
						minstep = dic[j + k]
				dic[j] = minstep + 1
				continue
			minstep = dic[j + 1]
			for k in range(2, min(length - j, nums[j] + 1)):
				if dic[j + k] < minstep:
					minstep = dic[j + k]
			dic[j] = minstep + 1
		return dic[0]