Dynamic Programming | O(n * n * fuel) | Memoization
DP\ndp[current_position][fuel_left] stores nuber of ways to reach finish from current_position and fuel_left fuel  \n# Transitions\ndp[current][fuel] -> dp[next
# **DP**\n`dp[current_position][fuel_left]` stores nuber of ways to reach `finish` from `current_position` and `fuel_left` fuel  \n# **Transitions**\n`dp[current][fuel] -> dp[next][fuel - distance]`\n## **Time Complexity**\n`O(n * n * fuel)`\n## **Space Complexity**\n`O(n * fuel)`\n\n# **Code CPP**\n```\nclass Solution {\npublic:\n    vector<vector<int>> dp;\n    const int mod = 1e9 + 7;\n    int go(int pos, int tar, int fuel, vector<int> &ar)\n    {\n        if (dp[pos][fuel] != -1)\n            return dp[pos][fuel];\n        int ans = 0;\n\t\t// ***** EASY TO MISS *****\n        if (pos == tar)\n            ans ++;\n        ans %= mod;\n\n        for (int i = 0; i < ar.size(); i++)\n        {\n            if (i != pos)\n            {\n                int dist = labs(ar[i] - ar[pos]);\n                {\n                    if (dist <= fuel)\n                    {\n                        ans += go(i, tar, fuel - dist, ar);\n                        ans %= mod;\n                    }\n                }\n            }\n        }\n        return dp[pos][fuel] = ans;\n    }\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        int n = locations.size();\n        dp = vector<vector<int>> (200, vector<int>(300, -1));\n        return go(start, finish, fuel, locations);\n    }\n};\n```
[]