C++(Recursive DP) | 112 ms (85.23% faster) | 8.6 MB (99.43% lesser) | Count All Possible Routes
This is the recursive dp solution. \ndp[ i ][ fuel ] = Number of ways to reach finish city from city i with currently available fuel.\nTime Complexity : O(f * N
This is the recursive dp solution. \ndp[ i ][ fuel ] = Number of ways to reach finish city from city i with currently available fuel.\nTime Complexity : O(f * N^2)\nSpace Complexity : O(f * N) where, f=fuel given and N=Number of cities.\n```\nclass Solution {\npublic:\n    int dp[100][201];\n    int mod = 1000000007;\n    \n    int rec(int i, int finish, int fuel, vector<int>&locations)\n    {\n        if(fuel<0)\n            return 0;\n        \n        if(dp[i][fuel]!=-1)\n            return dp[i][fuel];\n        \n        int n = locations.size(), ans=0;\n        \n        if(i==finish && fuel>=0)\n            ans++;\n        \n        for(int k=0; k<n; k++)\n        {\n            if(k==i)\n                continue;\n            ans+=rec(k, finish, fuel-abs(locations[i]-locations[k]), locations);\n            ans%=mod;\n        }\n        return dp[i][fuel] = ans;\n    }\n    \n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        memset(dp, -1, sizeof(dp));\n        return rec(start, finish, fuel, locations);\n    }\n};\n```
['Dynamic Programming', 'C']