跳躍游戲 II
題目描述：
給定一個非負整數(shù)數(shù)組俗或，你最初位于數(shù)組的第一個位置议慰。
數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度闸溃。
你的目標是使用最少的跳躍次數(shù)到達數(shù)組的最后一個位置胯努。
示例
輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數(shù)是 2东臀。
從下標為 0 跳到下標為 1 的位置楞艾，跳 1 步参咙，然后跳 3 步到達數(shù)組的最后一個位置。
說明:
假設你總是可以到達數(shù)組的最后一個位置硫眯。
解題思路：
主要利用貪心算法的動態(tài)規(guī)劃來解決問題
- 我們核心思想是盡可能多的跳躍到更遠的地方蕴侧，以來減少跳躍的次數(shù)，如果跳了一次之后還不能到两入，就需要多跳一次
- 首先創(chuàng)建三個參數(shù)
counter表示跳躍的次數(shù)净宵，curr_end表示當前起跳點的位置的下標，curr_farthest表示當前起跳點可以跳的最遠位置的下標 - 然后通過
curr_farthest = max(curr_farthest, i + nums[i])來更新最遠位置的下標裹纳，然后等到i遍歷到起跳點的時候择葡，如果此時還不是到最后，那就用最貪心的方式剃氧，從起跳點跳最遠距離curr_farthest敏储，直到我們到達終點
Python源碼：
from typing import List
class Solution:
def jump(self, nums: List[int]) -> int:
counter = 0 # 移動次數(shù)
curr_end = 0 # 當前跳躍的終點
curr_farthest = 0 # 最遠位置的下標
for i in range(len(nums) - 1):
curr_farthest = max(curr_farthest, i + nums[i])
if i == curr_end:
counter += 1
curr_end = curr_farthest
return counter
歡迎關(guān)注我的github：https://github.com/UESTCYangHR
