SDE-Challenge/Count-All-Possible-Routes.cpp at main · looneyd-rohit/SDE-Challenge · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Leetcode 1575
class Solution
{
public:
    const int M = 1e9 + 7;
    int solve(int city, vector<int> &locations, int fuel, int finish, vector<vector<int>> &dp)
    {
        // dp check
        if (dp[city][fuel] != -1)
            return dp[city][fuel];

        int ans = 0;
        // bool travelled = false;
        for (int i = 0; i < locations.size(); i++)
        {
            // visit next city if possible
            if (i != city)
            {
                if (fuel - abs(locations[i] - locations[city]) >= 0)
                {
                    ans += solve(i, locations, fuel - abs(locations[i] - locations[city]), finish, dp) % M;
                    ans = ans % M;
                }
            }
        }
        if (city == finish)
        {
            ans++;
        }
        return dp[city][fuel] = ans % M;
    }
    int countRoutes(vector<int> &locations, int start, int finish, int fuel)
    {
        int n = locations.size();
        // memoization:
        vector<vector<int>> dp(101, vector<int>(201, -1));
        return solve(start, locations, fuel, finish, dp) % M;
    }
};