C# DFS + DP
Approach\n- Use dynamic programming to solve this problem with each state defined by the city index and fuel left. So dp[i, fuel] is the state for the city i an
# Approach\n- Use dynamic programming to solve this problem with each state defined by the city index and fuel left. So `dp[i, fuel]` is the state for the city `i` and `fuel`\n- Use DFS to find number of routes from city `i`, `finish` city and `fuel`.\n\n# Complexity\n- Time complexity: $$O(n \\times fuel)$$\n- Space complexity: $$O(n \\times fuel)$$\n\n# Code\n```\npublic class Solution\n{\n    private const int Modulo = 1_000_000_007;\n    private int[,] _dp;\n    private int[] _locations;\n\n    public int CountRoutes(int[] locations, int start, int finish, int fuel)\n    {\n        _locations = locations;\n        _dp = new int[locations.Length, fuel + 1];\n\n        for (var i = 0; i < locations.Length; i++)\n        {\n            for (var j = 0; j < fuel + 1; j++)\n            {\n                _dp[i, j] = -1;\n            }\n        }\n\n        return dfs(start, finish, fuel);\n    }\n\n    private int dfs(int i, int finish, int fuel)\n    {\n        var n = _locations.Length;\n        if (fuel < 0)\n        {\n            return 0;\n        }\n\n        if (_dp[i, fuel] != -1)\n        {\n            return _dp[i, fuel];\n        }\n\n        var ans = 0;\n\n        if (i == finish)\n        {\n            ans++;\n        }\n\n        for (var j = 0; j < n; j++)\n        {\n            if (j == i)\n            {\n                continue;\n            }\n\n            ans = (ans + dfs(j, finish, fuel - Math.Abs(_locations[i] - _locations[j]))) % Modulo;\n        }\n\n        return _dp[i, fuel] = ans;\n    }\n}\n```
['C#']