C++ | Simplest YouTube Explanation | codestorywithMIK
YouTube Link - Count All Possible Routes\nMy Github Treasure - Count All Possible Routes\n\n\nclass Solution {\npublic:\n    const int MOD = 1e9+7;\n    int n;\
YouTube Link - [Count All Possible Routes](https://www.youtube.com/watch?v=qppd8vx0vK4)\nMy Github Treasure - [Count All Possible Routes](https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/Count%20All%20Possible%20Routes.cpp)\n\n```\nclass Solution {\npublic:\n    const int MOD = 1e9+7;\n    int n;\n    int t[101][201];\n    \n    int solve(vector<int>& locations, int currCity, int finish, int fuel) {\n        if (fuel < 0) {\n            return 0;\n        }\n\n        if(t[currCity][fuel] != -1)\n            return t[currCity][fuel];\n        \n        int ans = 0;\n        \n        if(currCity == finish)\n            ans++;\n        \n        for (int nextCity = 0; nextCity < locations.size(); nextCity++) {\n            \n            if (nextCity != currCity) {\n                int remaining_fuel = fuel - abs(locations[currCity] - locations[nextCity]);\n                \n                ans = (ans + solve(locations, nextCity, finish, remaining_fuel)) % MOD;\n            }\n        }\n\n        return t[currCity][fuel] = ans;\n    }\n\n    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {\n        n = locations.size();\n        memset(t, -1, sizeof(t));\n        return solve(locations, start, finish, fuel);\n    }\n};\n```
[]