403.go

// canCross(i, k): can cross at the ith unit when last jump was k units
// canCross(i, k) = canCross(i + k - 1, k-1) || canCross(i + k, k) || canCross(i + k + 1, k + 1)
// canCross(i, 1) = canCross(i, 0) || canCross(i + 1, 1) || canCross(i+2, 2)
var memo map[int]map[int]bool

func canCross(stones []int) bool {
    memo = make(map[int]map[int]bool, len(stones))
    stonesMap := make(map[int]bool, len(stones))
    for _, v := range stones {
        stonesMap[v] = true
    }
    return canCrossHelper(0, 0, stonesMap, stones[len(stones) - 1])
}

func canCrossHelper(i, k int, stones map[int]bool, target int) bool {
    if stones[i] == false {
        return false
    }
    
    if i == target {
        return true
    }
    
    if res, ok := memo[i][k]; ok {
        return res
    }
    
    c1, c2, c3 := false, false, false
    if k > 1 {
        c1 = canCrossHelper(i + k - 1, k - 1, stones, target)
    }
    if k > 0 {
        c2 = canCrossHelper(i + k, k, stones, target)
    }
    c3 = canCrossHelper(i + k + 1, k + 1, stones, target)
    
    if memo[i] == nil {
        memo[i] = make(map[int]bool)
    }
    
    memo[i][k] = c1 || c2 || c3
    return c1 || c2 || c3
}