45.跳跃游戏II

45.跳跃游戏II

题解

//state: dp[x]表示最少跳几次到达下标x
//function: dp[i] = min(dp[i], dp[j]+1)
//intialize:dp[i] = i
//answer: dp[len(dp)-1]

代码

package mainfunc jump(nums []int) int {dp := make([]int, len(nums))dp[0] = 0for i := 1; i < len(dp); i++ {dp[i] = ifor j := 0; j < i; j++ {if nums[j]+j >= i {dp[i] = min(dp[i], dp[j]+1)}}}return dp[len(nums)-1]
}
func min(a, b int) int {if a > b {return b}return a
}