Slightly optimized dp solution
The approach is the same as editorial but there is one additional optimization.\nBefore running algorithm, I sort the locations array.\nThis allows me to not it
The approach is the same as editorial but there is one additional optimization.\nBefore running algorithm, I sort the locations array.\nThis allows me to not iterate over all indexes of locations.\nI iterate to the lower and higher values only while it is possible to reach the finish.\n\n# Code\n```\npublic class Solution {\n    public int Mod = 1000000007;\n    public int[,] dp;\n    public int CountRoutes(int[] locations, int start, int finish, int fuel) {\n        dp = new int[locations.Length, 201];\n        var startValue = locations[start];\n        var finishValue = locations[finish];\n        Array.Sort(locations);\n        return dfs(locations, Array.IndexOf(locations, startValue), Array.IndexOf(locations, finishValue), fuel, dp);\n    }\n    public int dfs(int[] locations, int start, int finish, int fuel, int[,] dp)\n    {\n        if (dp[start, fuel] > 0) return dp[start, fuel];\n\n        var currentDistance = Math.Abs(locations[start] - locations[finish]);\n        if (currentDistance > fuel) return 0;\n\n        var res = 0;\n\n        if (locations[start] == locations[finish]) res++;\n\n        for (int i = start - 1; i >= 0; i--)\n        {\n            if (locations[start] - locations[i] + Math.Abs(locations[i] - locations[finish]) > fuel)\n            {\n                break;\n            }\n            else\n            {\n                res += dfs(locations, i, finish, fuel - locations[start] + locations[i], dp);\n                res %= Mod;\n            }\n        }\n\n        for (int i = start + 1; i < locations.Length; i++)\n        {\n            if (locations[i] - locations[start] + Math.Abs(locations[i] - locations[finish]) > fuel)\n            {\n                break;\n            }\n            else\n            {\n                res += dfs(locations, i, finish, fuel - locations[i] + locations[start], dp);\n                res %= Mod;\n            }\n        }\n\n        dp[start, fuel] = res;\n        return res;\n    }\n}\n```
['C#']