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 main func jump(nums []int) int { dp := make([]int, len(nums)) dp[0] = 0 for i := 1; i < len(dp); i++ { dp[i] = i for 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 }
