題目描述

給你一個(gè)非負(fù)整數(shù)數(shù)組 nums ，你最初位于數(shù)組的第一個(gè)位置。

數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度。

你的目標(biāo)是使用最少的跳躍次數(shù)到達(dá)數(shù)組的最后一個(gè)位置。

假設(shè)你總是可以到達(dá)數(shù)組的最后一個(gè)位置。

示例 1:
輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個(gè)位置的最小跳躍數(shù)是 2。
從下標(biāo)為 0 跳到下標(biāo)為 1 的位置，跳 1 步，然后跳 3 步到達(dá)數(shù)組的最后一個(gè)位置。

示例 2:
輸入: nums = [2,3,0,1,4]
輸出: 2

題解

思路1:正向遍歷
dp[i] 表示到達(dá)i點(diǎn)的最小布數(shù)
從0開始遍歷，計(jì)算由當(dāng)前點(diǎn)i所能到達(dá)的j點(diǎn)的dp[j] = min(dp[i]+1,dp[j]),dp[n-1] 即為結(jié)果

    static public func jump1(_ nums: [Int]) -> Int {
        let n = nums.count
        if n <= 1 {return 0}
        
        var dp = Array(repeating: Int.max/2, count: n)
        dp[0] = 0
        
        for i in 0..<n {
            var j = i+1
            let end = nums[i] + i
            
            while j <= end && j<n  {
                dp[j] = min(dp[i] + 1,dp[j])
                j += 1
            }
            
        }
        
        return dp[n-1]
        
    }

思路2:反向查找出發(fā)位置

由于總是可以到達(dá)數(shù)組的最后一個(gè)位置，因而數(shù)組中任意位置都可以到達(dá)

我們的目標(biāo)是到達(dá)數(shù)組的最后一個(gè)位置，因此我們可以考慮最后一步跳躍前所在的位置，該位置通過跳躍能夠到達(dá)最后一個(gè)位置。

如果有多個(gè)位置通過跳躍都能夠到達(dá)最后一個(gè)位置，我們可以「貪心」地選擇距離最后一個(gè)位置最遠(yuǎn)的那個(gè)位置，也就是對(duì)應(yīng)下標(biāo)最小的那個(gè)位置。因此，我們可以從左到右遍歷數(shù)組，選擇第一個(gè)滿足要求的位置。

找到最后一步跳躍前所在的位置之后，我們繼續(xù)貪心地尋找倒數(shù)第二步跳躍前所在的位置，以此類推，直到找到數(shù)組的開始位置

    static public func jump2(_ nums: [Int]) -> Int {
        let n = nums.count
        if n <= 1 {return 0}
        
        var steps = 0;
        var position = n-1

        while position>0 {
            for i in 0..<position {
                if nums[i] + i >= position {
                    position = i
                    steps += 1
                    break
                }
            }
        }
        
        return steps
        
    }

思路3:正向查找可到達(dá)的最大位置

如果我們「貪心」地進(jìn)行正向查找，每次找到可到達(dá)的最遠(yuǎn)位置，就可以在線性時(shí)間內(nèi)得到最少的跳躍次數(shù)

例如，對(duì)于數(shù)組 [2,3,1,2,4,2,3]，初始位置是下標(biāo) 0，從下標(biāo) 0 出發(fā)，最遠(yuǎn)可到達(dá)下標(biāo) 2。下標(biāo) 0 可到達(dá)的位置中，下標(biāo) 1 的值是 3，從下標(biāo) 1 出發(fā)可以達(dá)到更遠(yuǎn)的位置，因此第一步到達(dá)下標(biāo) 1。

從下標(biāo) 1 出發(fā)，最遠(yuǎn)可到達(dá)下標(biāo) 4。下標(biāo) 1 可到達(dá)的位置中，下標(biāo) 4 的值是 4 ，從下標(biāo) 4 出發(fā)可以達(dá)到更遠(yuǎn)的位置，因此第二步到達(dá)下標(biāo) 4

    static public func jump3(_ nums: [Int]) -> Int {
        let n = nums.count
        if n <= 1 {return 0}
        
        var steps = 0;
        var maxPosition = 0
        var curLoc = 0
        
        for i in 0..<n {
            if nums[i] + i >= maxPosition {
                var j = i+1
                while j <= nums[i] + i  && j<n {
                    if nums[j] + j >= maxPosition || nums[j] + j >= n-1 {
                        maxPosition = nums[j] + j
                        curLoc = j
                    }
                    j += 1
                }
                steps += 1
                
                if curLoc == n-1 {
                    break
                }
            }
        
            
        }
        return steps
        
    }

優(yōu)化

我們維護(hù)當(dāng)前能夠到達(dá)的最大下標(biāo)位置，記為邊界。我們從左到右遍歷數(shù)組，到達(dá)邊界時(shí)，更新邊界并將跳躍次數(shù)增加 1。

在遍歷數(shù)組時(shí)，我們不訪問最后一個(gè)元素，這是因?yàn)樵谠L問最后一個(gè)元素之前，我們的邊界一定大于等于最后一個(gè)位置，否則就無法跳到最后一個(gè)位置了。如果訪問最后一個(gè)元素，在邊界正好為最后一個(gè)位置的情況下，我們會(huì)增加一次「不必要的跳躍次數(shù)」，因此我們不必訪問最后一個(gè)元素

    static public func jump4(_ nums: [Int]) -> Int {
        let n = nums.count
        if n <= 1 {return 0}
        
        var steps = 0;
        var maxPosition = 0
        var end = 0
        for i in 0..<(n-1) {
            maxPosition = max(maxPosition, nums[i]+i)
            if i == end {
                steps += 1
                end = maxPosition
            }
            
        }
        return steps
        
    }

參考：https://leetcode-cn.com/problems/jump-game-ii
https://leetcode-cn.com/problems/jump-game-ii/solution/tiao-yue-you-xi-ii-by-leetcode-solution/