问题描述
Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
You can assume that you can always reach the last index.
Example 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [2,3,0,1,4]
Output: 2
Constraints:
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 10^5
问题分析
对于nums[i]来说，假设nums[i]为2，并且nums[i+1], nums[i+2]到达最后位置的最小跳数已知，那么就有 f(nums[i]) = min(f(nums[i+1]), f(nums[i+2])) + 1
通过简单例子分析，我们可以确定使用dp解决该问题，且状态转移方程为:
dp[i] = min(dp[i+1], dp[i+2], …, dp[i+nums[i]])
综上，代码如下:
实例代码
func jump(nums []int) int {
dp := make([]int, len(nums))
// 初始化dp数组为int最大值
for i := 0; i < len(nums); i++ {
dp[i] = math.MaxInt32
}
// base case: 对于最后一个元素来说，不需要经过任何jump就已经符合条件，故初始化为0
dp[len(nums)-1] = 0
for i := len(nums) - 2; i >= 0; i-- {
// 如果元素为0，则不可能再继续往后跳，故dp[i]为0
if nums[i] == 0 {
dp[i] = 0
continue
}
for j := 1; j <= nums[i] && i+j < len(nums); j++ {
// 跳过无法继续往后跳的case
if i+j < len(nums)-1 && dp[i+j] == 0 {
continue
}
// 状态转移方程
dp[i] = min(dp[i], dp[i+j]+1)
}
}
return dp[0]
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}