Golang - DFS && memo - 100%/100%
Intuition\nThere are only 200 fuel and 100 states, each turn at least 1 fuel is wasted, then there are less than 20100 possible positions to memoize and we can 
# Intuition\nThere are only 200 fuel and 100 states, each turn at least 1 fuel is wasted, then there are less than 20100 possible positions to memoize and we can do a depth-first search from start position. \n\n# Approach\n- Depth-first search with memoization of states we already visited \n\n# Complexity\n- Time complexity: O((len(locations) * fuel) * len(locations))\n- Space complexity: O(len(locations) * fuel) in the worst case\n\n# Optimisations: \n- memo: base approach is to use hash-map to memoize each state we visited. It is natural to memoize something like map where keys are integer arrays with size of 2, but it is also possible to memoize current position and fuel in one integer variable, because we know that there are less than 100 positions and less than 200 fuel: `state = curPos + curFuel * 100` \n- If we already have state approach, then we can replace map with fixed size 1-d array with size of 20100. This one optimisation get me from 200ms with map to 60ms and gives me 100% speed comparison with 7.0mb used. \n- The last optimisation idea I have is to replace fixed size array with the dynamic sized one. All state calculation logic is placed in function `toState`, so we need to replace function with `state = curPos + curFuel * len(locations)`\n\n# Code\n```\nconst mod = 1_000_000_007\n\nfunc abs(n int) int {\n    if n > 0 {\n        return n\n    }\n    return -n\n}\n\nfunc countRoutes(locations []int, start int, finish int, fuel int) int {\n    lenLoc := len(locations)\n    states := make([]int, lenLoc * (fuel + 1))\n    for i := range states {\n        states[i] = -1\n    }\n    toState := func(curPos, curFuel int) int {\n        return curPos + curFuel * lenLoc\n    }\n\n    var dfs func(curPos, curFuel int) int\n    dfs = func(curPos, curFuel int) int {\n        if states[toState(curPos, curFuel)] != -1 {\n            return states[toState(curPos, curFuel)]\n        }\n        res := 0\n        for nextPos := range locations {\n            if nextPos != curPos {\n                if abs(locations[curPos] - locations[nextPos]) <= curFuel {\n                    res += dfs(nextPos, curFuel - abs(locations[curPos] - locations[nextPos]))\n                }\n            }\n        }\n        if curPos == finish {\n            res += 1\n        }\n        states[toState(curPos, curFuel)] = res % mod\n        return res % mod\n    }\n    dfs(start, fuel)\n    return states[toState(start, fuel)]\n}\n```\n\n![image.png](https://assets.leetcode.com/users/images/9657d81b-efd8-40fc-8164-a0145c3886fb_1687683258.3781064.png)
['Depth-First Search', 'Memoization', 'Go']