參考45. 跳躍游戲 II。

題目

給定一個長度為 n 的 0 索引整數(shù)數(shù)組 nums。初始位置為 nums[0]。

每個元素 nums[i] 表示從索引 i 向前跳轉(zhuǎn)的最大長度。換句話說，如果你在 nums[i] 處，你可以跳轉(zhuǎn)到任意 nums[i + j] 處:0 <= j <= nums[i],i + j < n.
返回到達(dá) nums[n - 1] 的最小跳躍次數(shù)。生成的測試用例可以到達(dá) nums[n - 1]。

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

解題思路

• 動態(tài)規(guī)劃：考慮動態(tài)規(guī)劃求最小次數(shù),子問題為到達(dá)前一個位置的最小次數(shù)。

動態(tài)規(guī)劃

class Solution {
    public int jump(int[] nums) {
        //考慮動態(tài)規(guī)劃dp[i]表示到i位置最小跳躍次數(shù)
        int n = nums.length;
        int[] dp = new int[n];
        for(int i = 1; i < n; i++) {
            dp[i] = i;//Integer.MAX_VALUE;
            //遍歷上次可能的位置獲取最小次數(shù)
            for(int j = i-1; j < i && j >= 0; j--) {
                if(j + nums[j] >= i) dp[i] = Math.min(dp[i],dp[j]);
            }
            dp[i]++;
        }
        return dp[n - 1];
    }
}

復(fù)雜度分析

• 時間復(fù)雜度：O(n^2)，雙重循環(huán)遍歷。
• 空間復(fù)雜度：O(n)，dp數(shù)組空間n。