題目描述

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

每個元素 nums[i] 表示從索引 i 向后跳轉的最大長度。換句話說，如果你在 nums[i] 處，你可以跳轉到任意 nums[i + j] 處:

0 <= j <= nums[i]
i + j < n
返回到達 nums[n - 1] 的最小跳躍次數。生成的測試用例可以到達 nums[n - 1]。

class Solution {public int jump(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp,10001);dp[0] = 0;for(int i = 0; i < nums.length; i++){for(int j = 1; j <= nums[i] && i+j <nums.length; j++){dp[i+j] = Math.min(dp[i+j], dp[i] + 1);}}return dp[nums.length-1];}
}

小結：動規很容易想到，dp數組的含義是到達nums[i]最小步數，但這道題應該是貪心算法的題，貪心的解法二刷的時候再看吧。