[Java] Dynamic Programming with Video and Code
Solution\nWe always want to try to visit cities. By visiting city A from city B, our fuel drops by abs(arr[A] - arr[B]). If fuel ever goes below 0, there is no 
## Solution\nWe always want to try to visit cities. By visiting city A from city B, our fuel drops by abs(arr[A] - arr[B]). If fuel ever goes below 0, there is no solution. Each time we arrive at the goal city, there is 1 more possible solution. Don\'t stop traveling once the goal is reached, because we might be able to continue traveling and reach the destination.\n\nMake sure to cache each answer so subproblems aren\'t recalculated. Keep track of the current city and fuel. The cache array will look like: int[cities.length][fuel + 1]. \n\n## Video\n<iframe width="560" height="315" src="https://www.youtube.com/embed/npscijCCEek" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>\n\n## Complexity\nTime: O(n\\*n\\*f) = O(n^2\\*f)\nSpace: O(n\\*f)\n\n## Code\n\n```java\nclass Solution {\n    \n    static final int MOD = (int)Math.pow(10, 9) + 7;\n    int[][] cache;\n    \n    public int countRoutes(int[] locations, int start, int finish, int fuel) {\n        cache = new int[locations.length][fuel + 1];\n        for (int[] row : cache) \n            Arrays.fill(row, -1);\n        return dfs(locations, start, finish, fuel);\n    }\n    \n    public int dfs(int[] arr, int cur, int goal, int fuel) {\n        // Out of fuel, no solutions\n        if (fuel < 0) return 0;\n\n        // Already computed this state, return answer\n        if (cache[cur][fuel] != -1) {\n            return cache[cur][fuel];\n        }\n        \n        int result = 0;\n        \n        // Made it to where we want to be\n        if (cur == goal) {\n            result++;\n        }\n        \n        // Keep traveling\n        for (int i = 0; i < arr.length; i++) {\n            // Don\'t travel to where we already are\n            if (i == cur) continue;\n            int cost = Math.abs(arr[cur] - arr[i]);\n            int nextTrip = dfs(arr, i, goal, fuel - cost);\n            result += nextTrip;\n            result %= MOD;\n        }\n        \n        cache[cur][fuel] = result;\n        return result;\n    }\n}\n```
[]