BFS + Caching | Beats 100% | Detailed Explanation in Golang!!
Intuition\nAt first glance, this has to be tree discovery. With some caching, we can shorten the calculation time.\n\n# Approach\n Describe your approach to sol
# Intuition\nAt first glance, this has to be tree discovery. With some caching, we can shorten the calculation time.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nImagine finding a route is a discovery of path from root(start) to finish(leaf), the height of the tree is the fuel amount. However, the leaf could be at any level, i.e. doesn\'t have to use all the fuel to finish.\n\nSo we just need to know this - for every possible fuel amount left, what are the number of routes it has for the given destination. \n\n# Complexity\n- Time complexity: $$O(mn^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(max(mn, n^2))$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfunc countRoutes(locations []int, start int, finish int, fuel int) int {\n    // the discovery of routes is like discovering a tree starting from root start, with full fuel\n    // the results is actually the sum of all possible amount of left fuel at destination\n    // so we just need to decrement the fuel while discovering the routes\n    // and cache them in our location-fuel table\n\n    // this is BFS + caching, aka memorisation, aka DP\n    n := len(locations)\n    mod := int(1e9) + 7\n    dp := make([][]int, n)\n\n    // We don\' really need this usages map, but it\'s easier for deriving\n    // usages(0) = [0, 1, 4, 6, 2]\n    // usages(1) = [1, 0, 3, 5, 1]\n    // usages(2) = [4, 3, 0, 2, 2]\n    // usages(3) = [6, 5, 2, 0, 4]\n    // usages(4) = [2, 1, 2, 4, 0]\n    usages := make([][]int, n)\n    for i := 0; i < n; i++ {\n        usage := make([]int, n)\n        for j := 0; j < n; j++ {\n            usage[j] = diff(locations[i], locations[j])\n        }\n        usages[i] = usage\n    }\n\n    // e.g. Example 1\n    // starting from full fuel 5, l = start\n    // we can reach out to \n    // l  f0, 1, 2, 3, 4, 5\n    // 0  [0, 0, 0, 0, 0, 0]\n    // 1  [0, 0, 0, 0, 0, 1]\n    // 2  [0, 0, 0, 0, 0, 0]\n    // 3  [0, 0, 0, 0, 0, 0]  sum() is result\n    // 4  [0, 0, 0, 0, 0, 0]\n    for i := 0; i < n; i++ {\n        fuelLeft := make([]int, fuel + 1)\n        dp[i] = fuelLeft\n    }\n    dp[start][fuel]++\n\n    for f := fuel; f >= 0; f-- {\n        for l := 0; l < n; l++ {\n            lf := dp[l][f]\n            if lf > 0 {\n                // for each usage in the usages map\n                for i := 0; i < n; i++ {\n                    if usages[l][i] > 0 && usages[l][i] <= f && l != i {\n                        dp[i][f - usages[l][i]] += lf\n                        if dp[i][f - usages[l][i]] > mod {\n                            dp[i][f - usages[l][i]] = dp[i][f - usages[l][i]] % mod\n                        }\n                    }\n                }\n            }\n        }\n    }\n\n    sum := 0\n    for i := 0; i <= fuel; i++ {\n        sum += dp[finish][i]\n    }\n    return sum % mod\n}\n\nfunc diff(a int, b int) int {\n    if a - b < 0 {\n        return b - a\n    }\n    return a - b\n}\n```
['Dynamic Programming', 'Tree', 'Go']