Created
February 27, 2019 21:11
-
-
Save d8660091/b06bcef4ae05e3c157b19059af712666 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment