✅Easy Explanation | ✅C++ |✅ Dynamic Programming
🛣️ Count Routes - Dynamic Programming Approach📌 IntuitionThis problem can be solved using recursion with memoization, also known as dynamic programming.
We star
# 🛣️ Count Routes - Dynamic Programming Approach

## 📌 Intuition
This problem can be solved using **recursion with memoization**, also known as **dynamic programming**.

- We start from the **initial position** and explore all possible routes while ensuring that fuel is **greater than or equal to zero**.
- If we reach the **final destination**, we add `1` to our answer.
- However, there's a catch! Even after reaching the final destination, we can **visit another location and come back** to count as a **unique path**.
- Thus, we do not **immediately return the answer** upon reaching the destination but continue exploring **all possible paths**.

---

## 🛠 Approach
1. **Define a recursive function `solve(start, fuel, finish, locations, dp)`**:
   - If `fuel < 0`, return `0` (base case).
   - If we have already computed this state (`dp[start][fuel] ≠ -1`), return the **memoized result**.
   - If `start == finish`, initialize `curr = 1` (since we reached the target).
   - Iterate over all possible locations:
     - If we can move to another city (`fuel >= abs(locations[start] - locations[i])`), recursively calculate routes from that city.
     - Update `curr` using modulo `1e9 + 7`.
   - Store and return the computed result in `dp[start][fuel]`.

2. **Call `solve(start, fuel, finish, locations, dp)` from `countRoutes` function**:
   - Create a **DP table** `dp[n][fuel+1]` initialized with `-1` (for memoization).
   - Return the result modulo `1e9 + 7`.

---

## ⏳ Complexity Analysis
- **Time Complexity:** $$O(n \times fuel)$$  
  - **Reason:** We memoize each state `(start, fuel)`, leading to `O(n × fuel)` states.  
- **Space Complexity:** $$O(n \times fuel)$$  
  - **Reason:** We store results in a `dp[n][fuel+1]` array.

---

## 💻 Code Implementation (C++)
```cpp
class Solution {
public:
    int mod = 1e9 + 7;

    int solve(int start, int fuel, int finish, vector<int>& locations,
              vector<vector<long long>>& dp) {
        if (fuel < 0) return 0;
        if (dp[start][fuel] != -1) return dp[start][fuel] % mod;

        int curr = (start == finish) ? 1 : 0;
        for (int i = 0; i < locations.size(); i++) {
            if (start != i && abs(locations[start] - locations[i]) <= fuel) {
                curr = (curr % mod + solve(i, fuel - abs(locations[start] - locations[i]), 
                                           finish, locations, dp) % mod) % mod;
            }
        }
        return dp[start][fuel] = curr % mod;
    }

    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
        int n = locations.size();
        vector<vector<long long>> dp(n, vector<long long>(fuel + 1, -1));
        return solve(start, fuel, finish, locations, dp) % mod;
    }
};

['C++']