Count All Possible Routes LeetCode solution in C++

1
class Solution {
2
 public:
3
  int fun(vector<int> &arr, int s, int f, int k, vector<vector<int>> &dp) {
4
    if (k < 0) return 0;
5
    if (dp[s][k] != -1) return dp[s][k];
6
    int ans = 0;
7
    if (s == f) ans = 1;
8
    for (int i = 0; i < arr.size(); i++) {
9
      if (i != s) ans = (ans + fun(arr, i, f, k - abs(arr[s] - arr[i]), dp)) % 1000000007;
10
    }
11
    return dp[s][k] = ans;
12
  }
13

14
  int countRoutes(vector<int> &locations, int start, int finish, int fuel) {
15
    vector<vector<int>> dp(locations.size() + 1, vector<int>(fuel + 1, -1));
16
    int ans = fun(locations, start, finish, fuel, dp);
17
    return ans;
18
  }
19
};