Java || 8ms || DP bottom up iterative || O(N*fuel)
\nclass Solution {\n    static final int MOD = 1_000_000_007;\n    \n    public int countRoutes(int[] locations, int start, int finish, int fuel) {\n        int
```\nclass Solution {\n    static final int MOD = 1_000_000_007;\n    \n    public int countRoutes(int[] locations, int start, int finish, int fuel) {\n        int startLoc = locations[start];\n        int finishLoc = locations[finish];\n        if (finishLoc < startLoc) {         // If start loc lower than finish loc, \n            startLoc = locations[finish];   //   then swap start and finish to make \n            finishLoc = locations[start];   //   start ALWAYS lower than finish.\n        }\n        int fuelExtra = fuel - (finishLoc - startLoc);\n        if (fuelExtra < 0)  return 0;  // Not enough fuel to reach finish.\n        \n        Arrays.sort(locations);         // Sort the cities into increasing location order.\n        int n = locations.length;\n        int minLoc = startLoc - fuelExtra / 2;  // Min loc reachable while still finishing.\n        int maxLoc = finishLoc + fuelExtra / 2; // Max loc reachable while still finishing.\n        int firstIdx = 0;               // Index of lowest reachable city.\n        int lastIdx = n - 1;            // Index of highest reachable city.\n        for (int i = 0; i < n; i++) {   // Loop through cities low to high, to update values.\n            int loc = locations[i];\n            if (loc == startLoc)  start = i;\n            if (loc == finishLoc)  finish = i;\n            if (loc < minLoc)  firstIdx = i + 1;\n            if (loc <= maxLoc)  lastIdx = i;\n        }\n        if (firstIdx == lastIdx)  return 1;  // Start and finish are the same, \n                                             //   with no other cities reachable.\n        \n        // dp...[][] arrays are indexed by dp...[city][fuel used].\n        // dpLeft is for moving leftward (i.e. from higher location to lower location).\n        // dpRight is for moving rightward (i.e. from lower location to higher location).\n        // We know which cities have lower and higher locations, because the \n        // locations[] array was sorted into increasing location order.\n        int[][] dpLeft = new int[lastIdx + 1][fuel + 1];\n        int[][] dpRight = new int[lastIdx + 1][fuel + 1];\n        dpLeft[start][0] = 1;\n        dpRight[start][0] = 1;\n        \n        // Loop from trying moving from lowest fuel usage, to maximum fuel usage.\n        // i.e. Bottom-up iterative.\n        for (int fuelUsed = 0; fuelUsed <= fuel; fuelUsed++) {\n            // Process cities from higher locations to lower locations (i.e. moving leftward)\n            for (int toIdx = lastIdx - 1; toIdx >= firstIdx; toIdx--) {\n                int fuelRemaining = fuelUsed - (locations[toIdx + 1] - locations[toIdx]);\n                if (fuelRemaining > 0) \n                    dpLeft[toIdx][fuelUsed] = ((dpLeft[toIdx + 1][fuelRemaining] * 2) % MOD + \n                                               dpRight[toIdx + 1][fuelRemaining]) % MOD;\n                else if (fuelRemaining == 0)\n                    dpLeft[toIdx][fuelUsed] = dpRight[toIdx + 1][fuelRemaining];\n            }\n\n            // Process cities from lower locations to higher locations (i.e. moving rightward)\n            for (int toIdx = firstIdx + 1; toIdx <= lastIdx; toIdx++) {\n                int fuelRemaining = fuelUsed - (locations[toIdx] - locations[toIdx - 1]);\n                if (fuelRemaining > 0) \n                    dpRight[toIdx][fuelUsed] = ((dpRight[toIdx - 1][fuelRemaining] * 2) % MOD + \n                                                dpLeft[toIdx - 1][fuelRemaining]) % MOD;\n                else if (fuelRemaining == 0)\n                    dpRight[toIdx][fuelUsed] = dpLeft[toIdx - 1][fuelRemaining];\n            }\n        }\n\n        // Gather all the counts of routes, for the finish city, for all possible \n        // fuel usages, to get to the total number of routes to the finish.\n        long result = 0;\n        for (int fuelUsed = 0; fuelUsed <= fuel; fuelUsed++) \n            result += dpLeft[finish][fuelUsed] + dpRight[finish][fuelUsed];\n        if (start == finish) \n            result--;\n        \n        return (int)(result % MOD);\n    }\n}\n```\n**----- Clean code ---------------**\n```\nclass Solution {\n    static final int MOD = 1_000_000_007;\n    \n    public int countRoutes(int[] locations, int start, int finish, int fuel) {\n        int startLoc = locations[start];\n        int finishLoc = locations[finish];\n        if (finishLoc < startLoc) {\n            startLoc = locations[finish];\n            finishLoc = locations[start];\n        }\n        int fuelExtra = fuel - (finishLoc - startLoc);\n        if (fuelExtra < 0)  return 0;\n        \n        Arrays.sort(locations);\n        int n = locations.length;\n        int minLoc = startLoc - fuelExtra / 2;\n        int maxLoc = finishLoc + fuelExtra / 2;\n        int firstIdx = 0;\n        int lastIdx = n - 1;\n        for (int i = 0; i < n; i++) {\n            int loc = locations[i];\n            if (loc == startLoc)  start = i;\n            if (loc == finishLoc)  finish = i;\n            if (loc < minLoc)  firstIdx = i + 1;\n            if (loc <= maxLoc)  lastIdx = i;\n        }\n        if (firstIdx == lastIdx)  return 1;\n        \n        int[][] dpLeft = new int[lastIdx + 1][fuel + 1];\n        int[][] dpRight = new int[lastIdx + 1][fuel + 1];\n        dpLeft[start][0] = 1;\n        dpRight[start][0] = 1;\n        \n        for (int fuelUsed = 0; fuelUsed <= fuel; fuelUsed++) {\n            for (int toIdx = lastIdx - 1; toIdx >= firstIdx; toIdx--) {\n                int fuelRemaining = fuelUsed - (locations[toIdx + 1] - locations[toIdx]);\n                if (fuelRemaining > 0) \n                    dpLeft[toIdx][fuelUsed] = ((dpLeft[toIdx + 1][fuelRemaining] * 2) % MOD + \n                                               dpRight[toIdx + 1][fuelRemaining]) % MOD;\n                else if (fuelRemaining == 0)\n                    dpLeft[toIdx][fuelUsed] = dpRight[toIdx + 1][fuelRemaining];\n            }\n\n            for (int toIdx = firstIdx + 1; toIdx <= lastIdx; toIdx++) {\n                int fuelRemaining = fuelUsed - (locations[toIdx] - locations[toIdx - 1]);\n                if (fuelRemaining > 0) \n                    dpRight[toIdx][fuelUsed] = ((dpRight[toIdx - 1][fuelRemaining] * 2) % MOD + \n                                                dpLeft[toIdx - 1][fuelRemaining]) % MOD;\n                else if (fuelRemaining == 0)\n                    dpRight[toIdx][fuelUsed] = dpLeft[toIdx - 1][fuelRemaining];\n            }\n        }\n\n        long result = 0;\n        for (int fuelUsed = 0; fuelUsed <= fuel; fuelUsed++) \n            result += dpLeft[finish][fuelUsed] + dpRight[finish][fuelUsed];\n        if (start == finish) \n            result--;\n        \n        return (int)(result % MOD);\n    }\n}\n```
['Java']