leetcode-go/hard/403.frog-jump.go

func canCross(stones []int) bool {
	n := len(stones)
	m := make(map[int]int)
	for i := 1; i < n; i++ {
		m[stones[i]] = i
	}
	steps := make([][]int, n)
	steps[0] = []int{0}
	return dfs(stones, m, n, 0, &steps)
}

func dfs(stones []int, m map[int]int, n, i int, steps *[][]int) bool {
	if i == n-1 {
		return true
	}
	for _, l := range (*steps)[i] {
		for j := maxInt(1, l-1); j <= l+1; j++ {
			if idx, ok := m[stones[i]+j]; ok {
				(*steps)[idx] = append((*steps)[idx], j)
				if dfs(stones, m, n, idx, steps) {
					return true
				}
			}
		}
	}
	return false
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}