[C++] Simple recursive DP on city and fuel
Idea: start a path from the start city with fuel and try to make all possible valid moves.\n\nThen store the answer obtained for a (start city, fuel) config and
Idea: start a path from the `start` city with `fuel` and try to make all possible valid moves.\n\nThen store the answer obtained for a `(start city, fuel)` config and re-use to avoid re-calculation (here comes DP)\n1. When your start city is same as finish city:\n\t* \tadd 1 to possible paths as one path is completed\n\t* \tcontinue your recursion if fuel is sufficient\n2. if start is not same as finish city, just continue recursion and move to all possible valid cities.\n\nRecursion:\n```\nif fuel == 0:\n\treturn 0\nif start = finish\n\tf(start, fuel) = 1 + f(j, fuel)\nelse if start != finish\n\tf(start, fuel) = f(j, fuel)\n\nHere j is all possible valid cities which are reachable from start with given fuel except start.\n```\n\n```\nclass Solution {\npublic:\n    int mod = 1e9 + 7;\n    vector<vector<int>> dp;\n    int dfs(int s, int f, int fuel, vector<int>& loc) {\n        if(fuel < 0) {\n            return 0;\n        }\n        if(dp[fuel][s] != -1) {\n            return dp[fuel][s];\n        }\n        long long ans = 0;\n        if(s == f) {\n            ans = 1;\n        }\n        int i = s;\n        for(int j = 0; j < loc.size(); j++) {\n            if(i != j) {\n                int diff = abs(loc[i] - loc[j]);\n\n                if(fuel >= diff) {\n                    long long res = dfs(j, f, fuel - diff, loc);\n                    ans = (ans + res) % mod;\n                }\n            }\n        }\n        dp[fuel][s] = ans;\n        return ans;\n    }\n    int countRoutes(vector<int>& loc, int start, int finish, int fuel) {\n        int n = loc.size();\n        dp = vector<vector<int>> (fuel + 1, vector<int> (n + 1, -1));\n        long long ans = dfs(start, finish, fuel, loc);\n        return ans % mod;        \n    }\n};
[]