C++, O(N log N+N*fuel)  solution
\nclass Solution {\n    const int N=1000000007;\n    \npublic:\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        start=lo
```\nclass Solution {\n    const int N=1000000007;\n    \npublic:\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        start=locations[start];\n        finish=locations[finish];\n        sort(locations.begin(),locations.end());\n        start=find(locations.begin(),locations.end(),start)-locations.begin();\n        finish=find(locations.begin(),locations.end(),finish)-locations.begin();\n        int size=locations.size();\n        int j,f,d;\n        vector<vector<int>> Ldp(size,vector<int>(fuel+1,0));\n        vector<vector<int>> Rdp(size,vector<int>(fuel+1,0));\n        for(f=1;f<=fuel;f++){\n            Ldp[size-1][f]=0;\n            Rdp[0][f]=0;\n            for(j=0;j<size-1;j++){\n                d=locations[j+1]-locations[j];\n                if(f>d)\n                    Ldp[j][f]=(Rdp[j+1][f-d]+2*Ldp[j+1][f-d]%N)%N;\n                else\n                    Ldp[j][f]=1*(f==d)*(start==(j+1));\n            }\n            for(j=1;j<size;j++){\n                d=locations[j]-locations[j-1];\n                if(f>d)\n                    Rdp[j][f]=(Ldp[j-1][f-d]+2*Rdp[j-1][f-d]%N)%N;\n                else\n                    Rdp[j][f]=1*(f==d)*(start==(j-1));\n            }\n        }\n        int ans=1*(start==finish);\n        for(j=1;j<=fuel;j++) ans=((ans+Ldp[finish][j])%N+Rdp[finish][j])%N;\n        return ans;\n    }\n};\n```\n\nThe idea is: When you move, you either move rightward (to a city of larger location number) or leftward (to a city of smaller location number).\nSo, we sort the locations first and accordingly modify the "start" and "finish" first. Then we define Ldp(j,f) to be the number of methods to move from start to j using exactly f fuels, while the last move is toward left. Rdp(j,f) is similarly but the last move is toward right. (Under module, of course.)\nLet\'s consider Ldp(j,f). Since your last move is toward left, you must move toward right to k first, where k>j, and then keep moving toward left to j. When you move from k to j, you can choose whether to stay at city l for each j<l<k, so there are 2^(k-j-1) ways to keep moving toward left from k to j. Therefore we have\nLdp(j,f)=Rdp(j+1,f-d(j,j+1))+2Rdp(j+2,f-d(j,j+2))+4Rdp(j+3,f-d(j,j+3))+...,\nwhere d(i,j) is the distance between city i and j.\n\nWe also note that\nLdp(j+1,f)=Rdp(j+2,f-d(j+1,j+2))+2Rdp(j+3,f-d(j+1,j+3))+...\nand then it happens to be\nLdp(j,f)=Rdp(j+1,f-d(j,j+1))+2Ldp(j+1,f-d(j,j+1)).\nSimilarly, \nRdp(j,f)=Ldp(j-1,f-d(j,j-1))+2Rdp(j-1,f-d(j,j-1)).\n\nNow the dp costs only O(N* fuel). There remains some edge cases.\n\nps. I couldn\'t solve it in contest :(
[]