[ 25 - 06 - 23 ] [ C++ ] [ Dynamic Programming ]
Code\n\nclass Solution {\npublic:\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        const int n = locations.size();\n    
# Code\n```\nclass Solution {\npublic:\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        const int n = locations.size();\n        dp.resize(fuel + 1, vector<int>(n, -1));\n        \n        return solve(start, finish, fuel, locations);\n    }\nprivate:\n    vector<vector<int>> dp;\n    const int kMod = 1e9 + 7;\n    int solve(int currCity, int endCity, int fuel, const vector<int>& locations){\n        if(fuel < 0) return 0;\n        if(~dp[fuel][currCity])\n            return dp[fuel][currCity];\n        \n        int ans = (currCity == endCity);\n        for(int nextCity = 0; nextCity < locations.size(); ++nextCity)\n            if(nextCity != currCity){\n                ans = (ans + solve(nextCity, endCity, fuel - abs(locations[currCity] - locations[nextCity]), locations)) % kMod;\n            }\n        return dp[fuel][currCity] = ans;\n    }\n};\n```
['C++']