Top-Down DP | Easy Solution | C++ | Faster than 76%
I have commented the only line you need to understand\nHave a look and you will understand\n\n\t\t\tclass Solution {\n\t\t\tpublic:\n\t\t\tint mod = 1e9+7;\n\t\
I have commented the only line you need to understand\nHave a look and you will understand\n\n\t\t\tclass Solution {\n\t\t\tpublic:\n\t\t\tint mod = 1e9+7;\n\t\t\tint f(int i, int j, int fuel, vector<int>& nums, vector<vector<int>> &dp){\n\n\t\t\t\tlong cnt=0;\n\t\t\t\tif(i==j && fuel==0) return 1;\n\t\t\t\tif(i==j) cnt++;      // You only need to understand this line, i.e. if you are at finish point and you have fuel, then go traverse more and increase cnt by 1 becasue it was one of the possible ways to reach finish point.\n\t\t\t\tif(fuel<=0) return 0;\n\t\t\t\tif(dp[i][fuel]!=-1) return dp[i][fuel];\n\n\t\t\t\tfor(int k=0;k<nums.size();k++){\n\n\t\t\t\t\tif(k!=i && fuel>=abs(nums[i]-nums[k])) cnt= (cnt+f(k,j,fuel-abs(nums[i]-nums[k]),nums,dp))%mod;\n\t\t\t\t\t// k != i condition will secure going to infinitely many times to same city from same city\n\t\t\t\t}\n\t\t\t\treturn dp[i][fuel] = cnt%mod;\n\t\t\t}\n\t\t\tint countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n\t\t\t\tint n = locations.size();\n\t\t\t\tvector<vector<int>> dp(n,vector<int>(fuel+1,-1));\n\t\t\t\treturn f(start,finish,fuel,locations,dp);\n\n\t\t\t}\n\t\t};
['Dynamic Programming', 'C']