leetcode brush questions (127) - 1575. Count all feasible paths

gives you an array of distinct integers, where locations[i] represents the location of the ith city. At the same time, it gives you start, finish and fuel, which respectively represent the departure city, destination city and the total amount of gasoline you have initially.

In each step, if you are in city i , you can choose any city j such that j != i and 0 <= j < locations.length , and move to city j . The amount of gasoline consumed to move from city i to j is |locations[i] - locations[j]|, where |x| represents the absolute value of x.

Note that fuel cannot be negative at any time, and you can travel through any city more than once (both start and finish ).

Please return the number of all possible paths from start to finish.

Since the answer can be large, return it by taking the remainder of 10^9 + 7.

Example 1:

enter: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
 output: 4
 Explanation: Here are all possible paths, each using 5 units of gasoline:
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3

Example 2:

enter: locations = [4,3,1], start = 1, finish = 0, fuel = 6
 output: 5
 Explanation: The following are all possible paths:
1 -> 0,The amount of gasoline used is fuel = 1
1 -> 2 -> 0,The amount of gasoline used is fuel = 5
1 -> 2 -> 1 -> 0,The amount of gasoline used is fuel = 5
1 -> 0 -> 1 -> 0,The amount of gasoline used is fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0,The amount of gasoline used is fuel = 5

Example 3:

enter: locations = [5,2,1], start = 0, finish = 2, fuel = 3
 output: 0
 Explanation: There is no way to get from 0 to 2 using only 3 units of gasoline. Because the shortest path requires 4 units of gas.

hint:

2 <= locations.length <= 100
1 <= locations[i] <= 109
The integers in all locations are different from each other.
0 <= start, finish < locations.length
1 <= fuel <= 200

The data range is only , and many students will think of DFS.

But as we said before, due to the exponential complexity of pure DFS, the data range usually does not exceed 30.

However, Memoized Search works.

memoized search

If you want to implement DFS, there are usually the following steps:

Design the "input parameters" and "output parameters" of the recursive function
Set the exit of the recursive function (Base Case)
Write "minimum unit" processing logic
For most DFS s, steps 1 and 3 are easy to implement, and finding the Base Case is usually the hardest of the trilogy.

Taking this question as an example, let's analyze "How to find a Base Case".

First of all, it should be clear that the so-called Base Case is actually to determine what kind of situation is valid/invalid once.

For this question, looking for Base Case is actually to determine: under what circumstances, it is regarded as 0 paths; under what circumstances, it is regarded as 1 path.

Then in the DFS process, the number of valid cases (counted as 1 for the number of paths) is continuously accumulated as the answer.

This is the essence of DFS and the thought process of finding a Base Case.

Returning to this question, the establishment of the valid situation is very simple and straightforward. If our current location is the destination, then it is a valid path, and we can add 1 to the number of paths.

So how do you establish an invalid situation?

An intuitive feeling is that when the oil is exhausted and the location is not at , then even if it has come to an end, it is considered an "invalid situation" and the recursion can be terminated.

There's nothing wrong with this logically, but there are cases where the oil level can never be zero.

Consider the following sample data:

locations = [0,2,2,2], 
start = 0, 
finish = 3, 
fuel = 1

We are currently at 0 and want to get to 3, but we have 1 fuel and can't move anywhere.

That is, if we only consider fuel=0 as the Base Case, the recursion may not terminate.

Therefore, a further restriction is added: the amount of oil is not 0, but it cannot move to any position any more, which is also an "invalid situation" and can terminate the recursion.

At this point, we have completed the "trilogy of DFS", and then since the data range of this question exceeds 30, we need to add "memory search" to DFS.

The design of the cache is also very simple, just use the two-dimensional array cache[][] to record.

We use cache[i][fuel] to represent the "number of paths" to the target location starting from the location and under the premise that the current remaining fuel is fuel.

The reason why we can take the practice of "cache intermediate results" is because "in the case where i and fuel are determined, the number of paths to the destination is uniquely determined".

class Solution {
    int mod = 1000000007;
    
    // Register: used to record the results in a "specific state"
    // cache[i][fuel] represents the "number of paths" to the target position starting from position i and the current remaining fuel amount is fuel
    int[][] cache;
    
    public int countRoutes(int[] ls, int start, int end, int fuel) {
        int n = ls.length;
        
        // initialize register
        // The reason to initialize it to -1
        // It is to distinguish between "the number of paths in a certain state is 0" and "a certain state has not been calculated".
        cache = new int[n][fuel + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);
        }
        
        return dfs(ls, start, end, fuel);
    }
    
    /**
     * Calculate "Number of Paths"
     * @param ls Entry locations
     * @param u current location (subscript of ls)
     * @param end target position (subscript of ls)
     * @param fuel remaining oil
     * @return Starting at position u and the fuel amount is fuel, the "number of paths" to end
     */
    int dfs(int[] ls, int u, int end, int fuel) {
        // If there is already an answer in the cache, return directly
        if (cache[u][fuel] != -1) {
            return cache[u][fuel];
        }
        
        int n = ls.length;
        // base case 1: if the oil level is 0 and not at the target location
        // Write the result 0 to the buffer and return
        if (fuel == 0 && u != end) {
            cache[u][fuel] = 0;
            return 0;
        } 
        
        // base case 2: the oil level is not 0 and cannot reach anywhere
        // Write the result 0 to the buffer and return
        boolean hasNext = false;
        for (int i = 0; i < n; i++) {
            if (i != u) {
                int need = Math.abs(ls[u] - ls[i]);    
                if (fuel >= need) {
                    hasNext = true;
                    break;
                }
            }
        }
        if (fuel != 0 && !hasNext) {
            int a= cache[u][fuel] = u==end?1:0;
            return a;
        }
        
        // Calculate the amount of fuel as fuel, the number of paths from position u to end
        // Since each point can be traversed multiple times, if u = end, it is a path in itself
        int sum = u == end ? 1 : 0;
        for (int i = 0; i < n; i++) {
            if (i != u) {
                int need = Math.abs(ls[i] - ls[u]);
                if (fuel >= need) {
                    sum += dfs(ls, i, end, fuel - need);
                    sum %= mod;
                }
            }
        }
        cache[u][fuel] = sum;
        return sum;
    }
}

Simplified Base Case (Mining Properties)

Our "invalid case" Base Case can be simplified further.

Consider a question: if we start from a certain position i and cannot reach the target position in one step, is it possible to use multiple steps to reach the target position?

That is, if one step doesn't work, can you take multiple steps?

The answer is no.

Assuming that the location[i] of our current location is a, the location[finish] of the target location is b, the absolute value of the difference between the two is need, and the current fuel amount is fuel.

It cannot be reached in one step, indicating need>fuel.

And every time we move to a new position, the fuel consumption cost is the absolute value of the difference between the two positions.

Just because cost>=0, the fuel's fuel'<=fuel after we move to the new location.

In other words, even moving from position i to a new position cannot change the property of need > fuel.

If we start at a certain position u and cannot reach the destination finish in one step, we will never reach the destination.

class Solution {
    int mod = 1000000007;
    
    // Register: used to record the results in a "specific state"
    // cache[i][fuel] represents the "number of paths" to the target position starting from position i and the current remaining fuel amount is fuel
    int[][] cache;
    
    public int countRoutes(int[] ls, int start, int end, int fuel) {
        int n = ls.length;
        
        // initialize register
        // The reason to initialize it to -1
        // It is to distinguish between "the number of paths in a certain state is 0" and "a certain state has not been calculated".
        cache = new int[n][fuel + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);
        }
        
        return dfs(ls, start, end, fuel);
    }
    
    /**
     * Calculate "Number of Paths"
     * @param ls Entry locations
     * @param u current location (subscript of ls)
     * @param end target position (subscript of ls)
     * @param fuel remaining oil
     * @return Starting at position u and the fuel amount is fuel, the "number of paths" to end
     */
    int dfs(int[] ls, int u, int end, int fuel) {
        // If there is already an answer in the cache, return it directly
        if (cache[u][fuel] != -1) {
            return cache[u][fuel];
        }
        
        // If it cannot be reached in one step, it means that the end position cannot be reached from the position u.
        // Write the result 0 to the buffer and return
        int need = Math.abs(ls[u] - ls[end]);
        if (need > fuel) {
            cache[u][fuel] = 0;
            return 0;
        }
        
        int n = ls.length;
        // Calculate the amount of fuel as fuel, the number of paths from position u to end
        // Since each point can be traversed multiple times, if u = end, it is a path in itself
        int sum = u == end ? 1 : 0;
        for (int i = 0; i < n; i++) {
            if (i != u) {
                need = Math.abs(ls[i] - ls[u]);
                if (fuel >= need) {
                    sum += dfs(ls, i, end, fuel - need);
                    sum %= mod;
                }
            }
        }
        cache[u][fuel] = sum;
        return sum;
    }
}

Tags: Algorithm data structure leetcode

Posted by neonorange79 on Thu, 10 Nov 2022 01:19:00 +0300