DP Memoization || Easy C++ Solution with Intution+Approach
Intuition\n Describe your first thoughts on how to solve this problem. \n- We have to count the number of ways in which we start from the \'start\' city and wan
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- We have to count the number of ways in which we start from the \'start\' city and want to finish at the \'finish\' city, with the given condition that we can visit any city any number of times. \n- The first thing that comes to mind whenever we encounter such a problem of counting the number of ways, with or without limitations, is dynamic programming with recursion/memoization.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Initialize a 2D dp of size \'n\' by \'fuel+1\', where \'n\' is the length of the given vector of cities.\n- Call the solve function.\n- First, check the base case: whether we still have fuel left or if we are empty now and can\'t move.\n- If the answer for the current city is already stored, retrieve the data from the dp table.\n- Now, initialize a variable ans = 0.\n- Check if the currentCity is equal to the finish city or not. If it is equal to the finish city, increment the ans by 1 and continue performing operations instead of returning ans, because we can visit any city any number of times.\n- Iterate over the next cities we can move to, which are not equal to the current city, and call the solve function again after decrementing the amount of fuel that will be burnt during travel to the next city.Whatever the solve function returns, add it to the ans.\n- Return the ans while storing it in the dp table.\n\n# Complexity\n- Time complexity:O((n^2)*fuel)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n*fuel)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int mod=1e9+7;\n    int solve(vector<vector<int>>&dp,vector<int>&l,int current,int &finish,int fuel){\n        int n=l.size();\n        if(fuel<0)return 0;\n        if(dp[current][fuel]!=-1)return dp[current][fuel];\n        int ans=0;\n        if(current==finish)ans++;\n        for(int next=0;next<n;next++){\n            if(next!=current){\n                ans=(ans%mod+solve(dp,l,next,finish,fuel-abs(l[current]-l[next]))%mod)%mod;\n            }\n        }\n        return dp[current][fuel]=ans%mod;\n    }\n    int countRoutes(vector<int>& l, int start, int finish, int fuel) {\n        int n=l.size();\n        vector<vector<int>>dp(n,vector<int>(fuel+1,-1));\n        return solve(dp,l,start,finish,fuel);\n    }\n};\n```\n
['Dynamic Programming', 'Memoization', 'C++']