Commitb70881e

committed

fix jump-game-ii

1 parent4056779 commitb70881eCopy full SHA for b70881e

File tree

+21

-0

lines changed

+21

-0

lines changed

Lines changed: 21 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -356,6 +356,7 @@ func canJump(nums []int) bool {`
`356`	`356`	`>你的目标是使用最少的跳跃次数到达数组的最后一个位置。`
`357`	`357`
`358`	`358`	```go
	`359`	`+// v1动态规划（其他语言超时参考v2）`
`359`	`360`	`funcjump(nums []int)int {`
`360`	`361`	`// 状态：f[i] 表示从起点到当前位置最小次数`
`361`	`362`	`// 推导：f[i] = f[j],a[j]+j >=i,min(f[j]+1)`
`@@ -383,6 +384,26 @@ func min(a, b int) int {`
`383`	`384`	`}`
`384`	`385`	```
`385`	`386`
	`387`	+```go
	`388`	`+// v2 动态规划+贪心优化`
	`389`	`+funcjump(nums []int)int {`
	`390`	`+n:=len(nums)`
	`391`	`+f:=make([]int, n)`
	`392`	`+ f[0] =0`
	`393`	`+fori:=1; i < n; i++ {`
	`394`	`+// 取第一个能跳到当前位置的点即可`
	`395`	`+// 因为跳跃次数的结果集是单调递增的，所以贪心思路是正确的`
	`396`	`+idx:=0`
	`397`	`+for idx<n&&idx+nums[idx]<i{`
	`398`	`+ idx++`
	`399`	`+ }`
	`400`	`+ f[i]=f[idx]+1`
	`401`	`+ }`
	`402`	`+return f[n-1]`
	`403`	`+}`
	`404`	`+`
	`405`	+```
	`406`	`+`
`386`	`407`	`###[palindrome-partitioning-ii](https://leetcode-cn.com/problems/palindrome-partitioning-ii/)`
`387`	`408`
`388`	`409`	`>给定一个字符串_s_，将_s_ 分割成一些子串，使每个子串都是回文串。`

Comments

(0)