C++ Top-down DP with explanation
Solution 1. Top-down DP\n\nLet dp[i][j] be the count of all possible routes from city i with j fuel to city finish.\n\nThe initial state is dp[start][fuel].\n\n
## Solution 1. Top-down DP\n\nLet `dp[i][j]` be the count of all possible routes from city `i` with `j` fuel to city `finish`.\n\nThe initial state is `dp[start][fuel]`.\n\nAssume we can go from city `i` to city `k`, `dp[i][j] += dp[k][j - dist(i, k)]`.\n\nWhen `i == finish` and `j >= 0`, we should add `1` to `dp[i][j]`.\n\n```\ndp[i][j] = sum( dp[k][j - dist[i, k]] | j - dist[i, k] >= 0 )\n            + (i == start ? 1 : 0)\n```\n\n`dp[start][fuel]` is the answer.\n\n```cpp\n// OJ: https://leetcode.com/contest/biweekly-contest-34/problems/count-all-possible-routes/\n// Author: github.com/lzl124631x\n// Time: O(N^2 * F)\n// Space: O(NF)\nclass Solution {\n    long dp[101][201] = {}, mod = 1e9+7, finish;\n    int dist(vector<int> &A, int a, int b) {\n        return abs(A[a] - A[b]);\n    }\n    int dfs(vector<int> &A, int start, int fuel) {\n        if (dp[start][fuel]) return dp[start][fuel];\n        long ans = 0;\n        if (start == finish) ans++;\n        for (int i = 0; i < A.size(); ++i) {\n            if (i == start || dist(A, start, i) + dist(A, i, finish) > fuel) continue;\n            ans = (ans + dfs(A, i, fuel - dist(A, i, start))) % mod;\n        }\n        return dp[start][fuel] = ans;\n    }\npublic:\n    int countRoutes(vector<int>& A, int start, int finish, int fuel) {\n        this->finish = finish;\n        return dfs(A, start, fuel);\n    }\n};\n```
[]