✅ Beat 100% | ✨ O(N fuel) | 🏆 Most Optimal Solution | 👍 With Proof
Intuition\n Describe your first thoughts on how to solve this problem. \nCities are at distince locations so we can always sort them first.\n\nWe define the fol
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nCities are at distince locations so we can always sort them first.\n\nWe define the following functions:\n$\\mathcal{R}_i(x)$: route count for starting at $i$th city with fuel $x$, when **going right direction first**\n$\\mathcal{L}_i(x)$: route count for starting at $i$th city with fuel $x$, when **going left direction first**\n$D_{i, j}$: The distance between $i$th city and $j$th city.\nNote that since we have sorted the cities, $D_{i, j} = $ `location[j] - location[i]` assuming $j > i$.\n\nWe concluded that there is a simple recursion relation:\n$$\n\\mathcal{R}_i(x) = 2\\mathcal{R}_{i + 1}(x - D_{i, i + 1})\n + \\mathcal{L}_{i + 1}(x - D_{i, i + 1})\n + I_{i + 1\\text{ is the finish city and the fuel is enough}}\n$$\nand similarly\n$$\n\\mathcal{L}_i(x) = 2\\mathcal{L}_{i - 1}(x - D_{i-1, i})\n + \\mathcal{R}_{i - 1}(x - D_{i-1, i})\n + I_{i - 1\\text{ is the finish city and the fuel is enough}}\n$$\nWhere $I_\\text{condition}$ is the *indicator* function that takes value 1 if the condition is met and 0 if not.\nWe also used a hidden convention that functions return 0 if the argument (or index) is out of bounds.\n\n> For the proof of this relation, see the [Appendix](#appendix-proof) below\n\nUsing DP with this simple relation gives easy and efficient solution.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$\\Theta(N \\log N + NM)$ where $N$ is the city count and $M$ is the `fuel`.\nFor any non-trival $M$ this is basically $\\Theta(N M)$.\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$\\Theta(NM)$\n\n# Code\n```\nconst int kMod = 1000\'000\'007;\n\nint ModAdd(int64_t a, int64_t b) {\n  return (a + b) % kMod;\n}\n\nclass Solution {\npublic:\n  int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n    int start_location = locations[start];\n    int finish_location = locations[finish];\n    std::sort(locations.begin(), locations.end());\n    start = std::lower_bound(locations.begin(), locations.end(), start_location) - locations.begin();\n    finish = std::lower_bound(locations.begin(), locations.end(), finish_location) - locations.begin();\n    \n    const int N = locations.size();\n    const int M = fuel + 1;\n    vector<vector<int>> dpR(N, vector<int>(M));\n    vector<vector<int>> dpL(N, vector<int>(M));\n    for (int x = 1; x < M; ++x) {\n      for (int i = 1; i < N; ++i) {\n        int y = x - (locations[i] - locations[i - 1]);\n        if (y < 0) {\n          continue;\n        }\n        dpR[i - 1][x] = ModAdd(dpR[i][y] * 2, dpL[i][y]);\n        dpL[i][x] = ModAdd(dpL[i - 1][y] * 2, dpR[i - 1][y]);\n        if (i == finish) {\n          dpR[i - 1][x] = ModAdd(dpR[i - 1][x], 1);\n        }\n        if (i - 1 == finish) {\n          dpL[i][x] = ModAdd(dpL[i][x], 1);\n        }\n      }\n    }\n    int answer = dpR[start][fuel] + dpL[start][fuel];\n    if (start == finish) {\n      ++answer;\n    }\n    return answer % kMod;\n  }\n};\n```\n\n# Appendix: Proof\n\nWhen starting at the $i$th city and going right, we can have 4 choices:\n  * Go to $i+1$th city and then going right. This gives us $\\mathcal{R}_{i + 1}(x - D_{i, i + 1})$\n  * Go to $i+1$th city and then going left. This gives us $\\mathcal{L}_{i + 1}(x - D_{i, i + 1})$\n  * Skip the $i+1$th city. If you think about this case, it has actually the same route count as case 1 $\\mathcal{R}_{i + 1}(x - D_{i, i + 1})$\n  * Go to $i+1$th city and that is the finish city and we stay there.\n\nThe argument of going left is similar.\n\n
['Dynamic Programming', 'C++']