Count All Possible Routes || Easy C++ || DP
TC: O(N * N * Fuel)\nSC: O(N * Fuel)\n\nclass Solution {\npublic:\n    int n; vector<int> v;\n    int st,en;\n    vector<vector<int>> dp; \n    long long val=0,
TC: O(N * N * Fuel)\nSC: O(N * Fuel)\n```\nclass Solution {\npublic:\n    int n; vector<int> v;\n    int st,en;\n    vector<vector<int>> dp; \n    long long val=0, mod=1e9+7;\n    int calc(int i, int fl) {\n        if(fl==0) { //if fuel finished, the best case\n            if(i==en) return 1; //if at end then 1(valid path)\n            return 0;   \n        }   //not using i==en as return because of overlapping path, see tc2\n        if(dp[i][fl]!=-1) return dp[i][fl];\n        int ans=(i==en);        //if i==en, this is a valid path, include it\n        for(int j=0;j<n;j++) {\n            if(i==j) continue;  //cannot move to itself\n            if(fl>=abs(v[i]-v[j])) {    //for valid movement\n                ans+=calc(j,fl-abs(v[i]-v[j]));\n                ans%=mod;\n            }\n        }\n        return dp[i][fl]=ans%mod;\n    }\n    int countRoutes(vector<int>& words, int start, int end, int fuel) {\n        dp.clear();\n        v=words;\n        st=start; en=end;\n        n=v.size();\n        dp.resize(n+1, vector<int> (fuel+1,-1));\n        int ans=calc(st, fuel);\n        return ans;\n    }\n};\n```\n\nHappy Coding, also please upvote if you like it!
['Dynamic Programming', 'Recursion', 'Memoization', 'C']