Skip to content

Latest commit

 

History

History
223 lines (181 loc) · 6.43 KB

File metadata and controls

223 lines (181 loc) · 6.43 KB

English Version

题目描述

给你一个 互不相同 的整数数组,其中 locations[i] 表示第 i 个城市的位置。同时给你 startfinish 和 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 单位的汽油。

 

提示:

  • 2 <= locations.length <= 100
  • 1 <= locations[i] <= 109
  • 所有 locations 中的整数 互不相同 。
  • 0 <= start, finish < locations.length
  • 1 <= fuel <= 200

解法

方法一:记忆化搜索

Python3

class Solution:
    def countRoutes(
        self, locations: List[int], start: int, finish: int, fuel: int
    ) -> int:
        @cache
        def dfs(i, t):
            if abs(locations[i] - locations[finish]) > t:
                return 0
            res = int(i == finish)
            for j, v in enumerate(locations):
                if j != i:
                    if (cost := abs(locations[i] - v)) <= t:
                        res += dfs(j, t - cost)
            return res % mod

        mod = 10**9 + 7
        return dfs(start, fuel)

Java

class Solution {
    private int[][] f;
    private int[] locations;
    private int target;
    private static final int MOD = (int) 1e9 + 7;

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        int n = locations.length;
        f = new int[n + 1][fuel + 1];
        this.locations = locations;
        target = finish;
        for (int i = 0; i < f.length; ++i) {
            Arrays.fill(f[i], -1);
        }
        return dfs(start, fuel);
    }

    private int dfs(int i, int t) {
        if (f[i][t] != -1) {
            return f[i][t];
        }
        if (Math.abs(locations[i] - locations[target]) > t) {
            return 0;
        }
        int res = i == target ? 1 : 0;
        for (int j = 0; j < locations.length; ++j) {
            if (j != i) {
                int cost = Math.abs(locations[i] - locations[j]);
                if (cost <= t) {
                    res += dfs(j, t - cost);
                    res %= MOD;
                }
            }
        }
        f[i][t] = res;
        return res;
    }
}

C++

class Solution {
public:
    const int mod = 1e9 + 7;

    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
        int n = locations.size();
        vector<vector<int>> f(n + 1, vector<int>(fuel + 1, -1));
        return dfs(start, fuel, locations, finish, f);
    }

    int dfs(int i, int t, vector<int>& locations, int target, vector<vector<int>>& f) {
        if (f[i][t] != -1) return f[i][t];
        if (abs(locations[i] - locations[target]) > t) return 0;
        int res = i == target;
        for (int j = 0; j < locations.size(); ++j) {
            if (j == i) continue;
            int cost = abs(locations[i] - locations[j]);
            if (cost <= t) res = (res + dfs(j, t - cost, locations, target, f)) % mod;
        }
        f[i][t] = res;
        return res;
    }
};

Go

func countRoutes(locations []int, start int, finish int, fuel int) int {
	n := len(locations)
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, fuel+1)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	mod := int(1e9) + 7
	var dfs func(int, int) int
	dfs = func(i, t int) int {
		if f[i][t] != -1 {
			return f[i][t]
		}
		if abs(locations[i]-locations[finish]) > t {
			return 0
		}
		res := 0
		if i == finish {
			res++
		}
		for j, v := range locations {
			if j != i {
				cost := abs(locations[i] - v)
				if cost <= t {
					res = (res + dfs(j, t-cost)) % mod
				}
			}
		}
		f[i][t] = res
		return res
	}
	return dfs(start, fuel)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

...