Count All Possible Routes LeetCode solution in Java

1
/*
2

3
Using DFS and Memo :
4

5
1. We will start from start pos provided and will dfs travel to each other location .
6
2. each time we will see if we reach finish , we will increment the result . but we wont stop there if we have fuel left and continue travelling
7
3. if fuel goes negetive , we will return 0 , as there is no valid solution in that path
8
4. we will take dp[locations][fuel+1] to cache the result , to avoid recomputing .
9

10
*/
11

12
class Solution {
13

14
  int mod = (int) Math.pow(10, 9) + 7;
15
  int[][] dp;
16

17
  public int countRoutes(int[] locations, int start, int finish, int fuel) {
18

19
    dp = new int[locations.length][fuel + 1];
20

21
    for (int[] row : dp) {
22
      Arrays.fill(row, -1);
23
    }
24

25
    return dfs(locations, start, finish, fuel);
26
  }
27

28
  public int dfs(int[] locations, int cur_location, int finish, int fuel) {
29

30
    if (fuel < 0) {
31
      return 0;
32
    }
33

34
    if (dp[cur_location][fuel] != -1) {
35
      return dp[cur_location][fuel];
36
    }
37

38
    int result = 0;
39

40
    if (cur_location == finish) {
41
      result++;
42
    }
43

44
    for (int i = 0; i < locations.length; i++) {
45

46
      if (i == cur_location) continue;
47

48
      int fuel_cost = Math.abs(locations[i] - locations[cur_location]);
49
      int next_trip = dfs(locations, i, finish, fuel - fuel_cost);
50
      result += next_trip;
51
      result %= mod;
52
    }
53

54
    dp[cur_location][fuel] = result;
55

56
    return dp[cur_location][fuel];
57
  }
58
}