LeetCode_數組_中等_45.跳躍遊戲II

這裡寫目錄标題

• 1.題目
• 2.思路
• 3.代碼實作（Java）

1.題目

給你一個非負整數數組 nums ，你最初位于數組的第一個位置。

數組中的每個元素代表你在該位置可以跳躍的最大長度。

你的目标是使用最少的跳躍次數到達數組的最後一個位置。

假設你總是可以到達數組的最後一個位置。

示例 1：

輸入: nums = [2,3,1,1,4]

輸出: 2

解釋: 跳到最後一個位置的最小跳躍數是 2。從下标為 0 跳到下标為 1 的位置，跳 1 步，然後跳 3 步到達數組的最後一個位置。

示例 2：

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

輸出: 2

提示：

1 <= nums.length <= 104

0 <= nums[i] <= 1000

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/jump-game-ii

2.思路

（1）動态規劃

使用動态規劃最重要的一點就是找出狀态轉移方程，這裡定義一個長度為nums.length數組dp，且dp[i]=j表示從數組下标為0的位置跳到下标為 i 的位置需要的最少跳躍次數為 j，dp[0]=0。然後從數組nums中下标為1的元素開始周遊，并且計算dp[i]的值，當周遊結束後，dp[nums.length-1]的值即為題目所求，将其直接傳回即可。

那麼現在的關鍵在于如何求出dp[i]，可以這樣考慮，對于目前元素nums[i]，先從下标為0的位置開始尋找第一個可以直接跳到目前下标為i的位置 j，并且根據前面的定義可知dp[j]已經是從數組下标為0的位置跳到下标為 j 的位置需要的最少跳躍次數，是以可以推出狀态轉移方程為dp[i]=dp[j]+1，然後根據這來編寫代碼即可。

3.代碼實作（Java）

//（1）動态規劃
public int jump(int[] nums) {
    int length=nums.length;
    //dp[i]=j:從數組下标為0的位置跳到下标為i的位置需要的最少跳躍次數為j
    int[] dp=new int[length];
    dp[0]=0;
    for(int i=1;i<length;i++){
    	//從下标為0的位置開始尋找第一個可以直接跳到目前下标為i的位置
        int j=0;
        //nums[j]<i-j:說明從下标為j的位置不能直接跳到目前下标為i的位置
        //j++:将跳躍位置向後移動一個長度
        while(j<i && nums[j]<i-j){
            j++;
        }
        //此時已找到第一個可以直接跳到目前下标為i的位置j，且dp[j]是從數組下标為0的位置跳到下标為j的位置需要的最少跳躍次數
        dp[i]=dp[j]+1;
    }
    return dp[length-1];
}