列表

详情

1575. 统计所有可行路径

给你一个 互不相同 的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量

每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足  j != i 且 0 <= j < locations.length ，并移动到城市 j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。

请注意， fuel 任何时刻都 不能 为负，且你 可以 经过任意城市超过一次（包括 start 和 finish ）。

请你返回从 start 到 finish 所有可能路径的数目。

由于答案可能很大， 请将它对 10^9 + 7 取余后返回。

 

示例 1：

输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
输出：4
解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3

示例 2：

输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6
输出：5
解释：以下为所有可能的路径：
1 -> 0，使用汽油量为 fuel = 1
1 -> 2 -> 0，使用汽油量为 fuel = 5
1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5

示例 3：

输入：locations = [5,2,1], start = 0, finish = 2, fuel = 3
输出：0
解释：没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int countRoutes(vector<int>& locations, int start, int finish, int fuel) { } };

golang 解法, 执行用时: 84 ms, 内存消耗: 6.4 MB, 提交时间: 2023-09-27 07:52:58 

// 路径数统计
// 一维轴，loc[i]处有城市
// s t 是起始和终止位置
// f是初始汽油量，汽油量不可以为负
// 路径认为是城市的序列，统计s开始，t结束的可能路径数
// len(loc) is up to 100, f is up to 200
func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

// DFS 解法
func countRoutes2(loc []int, s int, t int, f int) int {
    MOD := int(1e9+7)
    // dp[i][j] 记录i城，剩j汽油到t的路径数
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        if j < 0 {
            return 0
        }

        res := 0
        if i == t {
            res++
        }

        for next := 0; next < len(loc); next++ {
            if next == i {
                continue
            }
            res += dfs(next, j - abs(loc[i]-loc[next])) % MOD
        }
        return res % MOD
        // dp[i][j] = 
        // i == t, 
        //   1 + for next != i dp[i][j] += dp[next][j-abs(loc[i]-loc[next])] % MOD
        //   0 + see above
        // dp[i][j] %= MOD
    }

    return dfs(s, f)
}

// DP 解法
func countRoutes(loc []int, s int, t int, f int) int {
    MOD := int(1e9+7)
    n := len(loc)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, f + 1)
    }
    for j := 0; j <= f; j++ {
        for i := 0; i < n; i++ {
            if j == f && i != s {
                continue
            }
            if i == t {
                dp[i][j] = 1
            }
            for next := 0; next < n; next++ {
                if next != i {
                    col := j-abs(loc[i]-loc[next])
                    // assert col < j
                    if col >= 0 {
                        dp[i][j] += dp[next][col]
                    }
                }
            }
            dp[i][j] %= MOD
        }
    }
    return dp[s][f]
}

cpp 解法, 执行用时: 24 ms, 内存消耗: 15 MB, 提交时间: 2023-09-27 07:52:07 

class Solution {
private:
    static constexpr int mod = 1000000007;

public:
    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
        int n = locations.size();
        int startPos = locations[start];
        int finishPos = locations[finish];
        sort(locations.begin(), locations.end());
        for (int i = 0; i < n; ++i) {
            if (startPos == locations[i]) {
                start = i;
            }
            if (finishPos == locations[i]) {
                finish = i;
            }
        }

        vector<vector<int>> dpL(n, vector<int>(fuel + 1));
        vector<vector<int>> dpR(n, vector<int>(fuel + 1));
        dpL[start][0] = dpR[start][0] = 1;
        
        for (int used = 0; used <= fuel; ++used) {
            for (int city = n - 2; city >= 0; --city) {
                if (int delta = locations[city + 1] - locations[city]; used >= delta) {
                    dpL[city][used] = ((used == delta ? 0 : dpL[city + 1][used - delta]) * 2 % mod + dpR[city + 1][used - delta]) % mod;
                }
            }
            for (int city = 1; city < n; ++city) {
                if (int delta = locations[city] - locations[city - 1]; used >= delta) {
                    dpR[city][used] = ((used == delta ? 0 : dpR[city - 1][used - delta]) * 2 % mod + dpL[city - 1][used - delta]) % mod;
                }
            }
        }

        int ans = 0;
        for (int used = 0; used <= fuel; ++used) {
            ans += (dpL[finish][used] + dpR[finish][used]) % mod;
            ans %= mod;
        }
        if (start == finish) {
            ans = (ans + mod - 1) % mod;
        }
        return ans;
    }
};

java 解法, 执行用时: 9 ms, 内存消耗: 41.9 MB, 提交时间: 2023-09-27 07:51:50 

class Solution {
    static final int MOD = 1000000007;

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        int n = locations.length;
        int startPos = locations[start];
        int finishPos = locations[finish];
        Arrays.sort(locations);
        for (int i = 0; i < n; ++i) {
            if (startPos == locations[i]) {
                start = i;
            }
            if (finishPos == locations[i]) {
                finish = i;
            }
        }

        int[][] dpL = new int[n][fuel + 1];
        int[][] dpR = new int[n][fuel + 1];
        dpL[start][0] = dpR[start][0] = 1;
        
        for (int used = 0; used <= fuel; ++used) {
            for (int city = n - 2; city >= 0; --city) {
                int delta = locations[city + 1] - locations[city];
                if (used >= delta) {
                    dpL[city][used] = ((used == delta ? 0 : dpL[city + 1][used - delta]) * 2 % MOD + dpR[city + 1][used - delta]) % MOD;
                }
            }
            for (int city = 1; city < n; ++city) {
                int delta = locations[city] - locations[city - 1];
                if (used >= delta) {
                    dpR[city][used] = ((used == delta ? 0 : dpR[city - 1][used - delta]) * 2 % MOD + dpL[city - 1][used - delta]) % MOD;
                }
            }
        }

        int ans = 0;
        for (int used = 0; used <= fuel; ++used) {
            ans += (dpL[finish][used] + dpR[finish][used]) % MOD;
            ans %= MOD;
        }
        if (start == finish) {
            ans = (ans + MOD - 1) % MOD;
        }
        return ans;
    }
}

python3 解法, 执行用时: 236 ms, 内存消耗: 17.2 MB, 提交时间: 2023-09-27 07:51:36 

class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        mod = 10**9 + 7

        n = len(locations)
        startPos = locations[start]
        finishPos = locations[finish]
        locations.sort()
        start = locations.index(startPos)
        finish = locations.index(finishPos)

        dpL = [[0] * (fuel + 1) for _ in range(n)]
        dpR = [[0] * (fuel + 1) for _ in range(n)]
        dpL[start][0] = dpR[start][0] = 1
        
        for used in range(fuel + 1):
            for city in range(n - 2, -1, -1):
                if (delta := locations[city + 1] - locations[city]) <= used:
                    dpL[city][used] = ((0 if used == delta else dpL[city + 1][used - delta]) * 2 + dpR[city + 1][used - delta]) % mod
            for city in range(1, n):
                if (delta := locations[city] - locations[city - 1]) <= used:
                    dpR[city][used] = ((0 if used == delta else dpR[city - 1][used - delta]) * 2 + dpL[city - 1][used - delta]) % mod

        ans = sum(dpL[finish]) + sum(dpR[finish])
        if start == finish:
            ans -= 1
        return ans % mod

python3 解法, 执行用时: 988 ms, 内存消耗: 21.5 MB, 提交时间: 2023-09-27 07:51:14 

class Solution:
    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:
        n = len(locations)
        
        @lru_cache(None)
        def dfs(pos, rest):
            if abs(locations[pos] - locations[finish]) > rest:
                return 0
                
            ans = 0
            for i, loc in enumerate(locations):
                if pos != i:
                    cost = abs(locations[pos] - loc)
                    if cost <= rest:
                        ans += dfs(i, rest - cost)
            if pos == finish:
                ans += 1
            return ans % 1000000007
                        
        return dfs(start, fuel)

cpp 解法, 执行用时: 144 ms, 内存消耗: 11.9 MB, 提交时间: 2023-09-27 07:50:40 

class Solution {
private:
    static constexpr int mod = 1000000007;
    vector<vector<int>> f;
    
public:
    int dfs(const vector<int>& locations, int pos, int finish, int rest) {
        if (f[pos][rest] != -1) {
            return f[pos][rest];
        }
        
        f[pos][rest] = 0;
        if (abs(locations[pos] - locations[finish]) > rest) {
            return 0;
        }
        
        int n = locations.size();
        for (int i = 0; i < n; ++i) {
            if (pos != i) {
                if (int cost = abs(locations[pos] - locations[i]); cost <= rest) {
                    f[pos][rest] += dfs(locations, i, finish, rest - cost);
                    f[pos][rest] %= mod;
                }
            }
        }
        if (pos == finish) {
            f[pos][rest] += 1;
            f[pos][rest] %= mod;
        }
        return f[pos][rest];
    }
    
    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
        f.assign(locations.size(), vector<int>(fuel + 1, -1));
        return dfs(locations, start, finish, fuel);
    }
};

java 解法, 执行用时: 49 ms, 内存消耗: 41.7 MB, 提交时间: 2023-09-27 07:50:21 

//  f[pos][rest] 表示当我们当前位于第 pos 个城市，剩余的汽油量为 rest 时，
// 到达终点 finish 的可能的路径总数。
class Solution {
    static final int MOD = 1000000007;
    int[][] f;

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        f = new int[locations.length][fuel + 1];
        for (int[] row : f) {
            Arrays.fill(row, -1);
        }
        return dfs(locations, start, finish, fuel);
    }

    public int dfs(int[] locations, int pos, int finish, int rest) {
        if (f[pos][rest] != -1) {
            return f[pos][rest];
        }
        
        f[pos][rest] = 0;
        if (Math.abs(locations[pos] - locations[finish]) > rest) {
            return 0;
        }
        
        int n = locations.length;
        for (int i = 0; i < n; ++i) {
            if (pos != i) {
                int cost;
                if ((cost = Math.abs(locations[pos] - locations[i])) <= rest) {
                    f[pos][rest] += dfs(locations, i, finish, rest - cost);
                    f[pos][rest] %= MOD;
                }
            }
        }
        if (pos == finish) {
            f[pos][rest] += 1;
            f[pos][rest] %= MOD;
        }
        return f[pos][rest];
    }
}

上一题

© 2024 leetcode.cn