Skip to content

Latest commit

 

History

History
413 lines (345 loc) · 12.3 KB

File metadata and controls

413 lines (345 loc) · 12.3 KB
comments difficulty edit_url rating source tags
true
困难
2055
第 34 场双周赛 Q4
记忆化搜索
数组
动态规划

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

解法

方法一:记忆化搜索

我们设计一个函数 $dfs(i, k)$,表示从城市 $i$ 出发,剩余汽油量为 $k$ 时,到达目的地 $finish$ 的路径数。那么答案就是 $dfs(start, fuel)$

函数 $dfs(i, k)$ 的计算过程如下:

  • 如果 $k \lt |locations[i] - locations[finish]|$,那么返回 $0$
  • 如果 $i = finish$,那么答案路径数初始时为 $1$,否则为 $0$
  • 然后,我们遍历所有城市 $j$,如果 $j \ne i$,那么我们可以从城市 $i$ 移动到城市 $j$,此时剩余汽油量为 $k - |locations[i] - locations[j]|$,那么我们可以将答案路径数加上 $dfs(j, k - |locations[i] - locations[j]|)$
  • 最后,我们返回答案路径数。

为了避免重复计算,我们可以使用记忆化搜索。

时间复杂度 $O(n^2 \times m)$,空间复杂度 $O(n \times m)$。其中 $n$$m$ 分别是数组 $locations$$fuel$ 的大小。

Python3

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

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

Java

class Solution {
    private int[] locations;
    private int finish;
    private int n;
    private Integer[][] f;
    private final int mod = (int) 1e9 + 7;

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        n = locations.length;
        this.locations = locations;
        this.finish = finish;
        f = new Integer[n][fuel + 1];
        return dfs(start, fuel);
    }

    private int dfs(int i, int k) {
        if (k < Math.abs(locations[i] - locations[finish])) {
            return 0;
        }
        if (f[i][k] != null) {
            return f[i][k];
        }
        int ans = i == finish ? 1 : 0;
        for (int j = 0; j < n; ++j) {
            if (j != i) {
                ans = (ans + dfs(j, k - Math.abs(locations[i] - locations[j]))) % mod;
            }
        }
        return f[i][k] = ans;
    }
}

C++

class Solution {
public:
    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
        int n = locations.size();
        int f[n][fuel + 1];
        memset(f, -1, sizeof(f));
        const int mod = 1e9 + 7;
        function<int(int, int)> dfs = [&](int i, int k) -> int {
            if (k < abs(locations[i] - locations[finish])) {
                return 0;
            }
            if (f[i][k] != -1) {
                return f[i][k];
            }
            int ans = i == finish;
            for (int j = 0; j < n; ++j) {
                if (j != i) {
                    ans = (ans + dfs(j, k - abs(locations[i] - locations[j]))) % mod;
                }
            }
            return f[i][k] = ans;
        };
        return dfs(start, fuel);
    }
};

Go

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

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

TypeScript

function countRoutes(locations: number[], start: number, finish: number, fuel: number): number {
    const n = locations.length;
    const f = Array.from({ length: n }, () => Array(fuel + 1).fill(-1));
    const mod = 1e9 + 7;
    const dfs = (i: number, k: number): number => {
        if (k < Math.abs(locations[i] - locations[finish])) {
            return 0;
        }
        if (f[i][k] !== -1) {
            return f[i][k];
        }
        let ans = i === finish ? 1 : 0;
        for (let j = 0; j < n; ++j) {
            if (j !== i) {
                const x = Math.abs(locations[i] - locations[j]);
                ans = (ans + dfs(j, k - x)) % mod;
            }
        }
        return (f[i][k] = ans);
    };
    return dfs(start, fuel);
}

方法二:动态规划

我们也可以将方法一的记忆化搜索转换为动态规划。

我们定义 $f[i][k]$ 表示从城市 $i$ 出发,剩余汽油量为 $k$ 时,到达目的地 $finish$ 的路径数。那么答案就是 $f[start][fuel]$。初始时 $f[finish][k]=1$,其余均为 $0$

接下来,我们从小到大枚举剩余汽油量 $k$,然后枚举所有的城市 $i$,对于每个城市 $i$,我们枚举所有的城市 $j$,如果 $j \ne i$,并且 $|locations[i] - locations[j]| \le k$,那么我们可以从城市 $i$ 移动到城市 $j$,此时剩余汽油量为 $k - |locations[i] - locations[j]|$,那么我们可以将答案路径数加上 $f[j][k - |locations[i] - locations[j]|]$

最后,我们返回答案路径数 $f[start][fuel]$ 即可。

时间复杂度 $O(n^2 \times m)$,空间复杂度 $O(n \times m)$。其中 $n$$m$ 分别是数组 $locations$$fuel$ 的大小。

Python3

class Solution:
    def countRoutes(
        self, locations: List[int], start: int, finish: int, fuel: int
    ) -> int:
        mod = 10**9 + 7
        n = len(locations)
        f = [[0] * (fuel + 1) for _ in range(n)]
        for k in range(fuel + 1):
            f[finish][k] = 1
        for k in range(fuel + 1):
            for i in range(n):
                for j in range(n):
                    if j != i and abs(locations[i] - locations[j]) <= k:
                        f[i][k] = (
                            f[i][k] + f[j][k - abs(locations[i] - locations[j])]
                        ) % mod
        return f[start][fuel]

Java

class Solution {
    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        final int mod = (int) 1e9 + 7;
        int n = locations.length;
        int[][] f = new int[n][fuel + 1];
        for (int k = 0; k <= fuel; ++k) {
            f[finish][k] = 1;
        }
        for (int k = 0; k <= fuel; ++k) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (j != i && Math.abs(locations[i] - locations[j]) <= k) {
                        f[i][k] = (f[i][k] + f[j][k - Math.abs(locations[i] - locations[j])]) % mod;
                    }
                }
            }
        }
        return f[start][fuel];
    }
}

C++

class Solution {
public:
    int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
        const int mod = 1e9 + 7;
        int n = locations.size();
        int f[n][fuel + 1];
        memset(f, 0, sizeof(f));
        for (int k = 0; k <= fuel; ++k) {
            f[finish][k] = 1;
        }
        for (int k = 0; k <= fuel; ++k) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (j != i && abs(locations[i] - locations[j]) <= k) {
                        f[i][k] = (f[i][k] + f[j][k - abs(locations[i] - locations[j])]) % mod;
                    }
                }
            }
        }
        return f[start][fuel];
    }
};

Go

func countRoutes(locations []int, start int, finish int, fuel int) int {
	n := len(locations)
	const mod = 1e9 + 7
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, fuel+1)
	}
	for k := 0; k <= fuel; k++ {
		f[finish][k] = 1
	}
	for k := 0; k <= fuel; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if j != i && abs(locations[i]-locations[j]) <= k {
					f[i][k] = (f[i][k] + f[j][k-abs(locations[i]-locations[j])]) % mod
				}
			}
		}
	}
	return f[start][fuel]
}

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

TypeScript

function countRoutes(locations: number[], start: number, finish: number, fuel: number): number {
    const n = locations.length;
    const f = Array.from({ length: n }, () => Array(fuel + 1).fill(0));
    for (let k = 0; k <= fuel; ++k) {
        f[finish][k] = 1;
    }
    const mod = 1e9 + 7;
    for (let k = 0; k <= fuel; ++k) {
        for (let i = 0; i < n; ++i) {
            for (let j = 0; j < n; ++j) {
                if (j !== i && Math.abs(locations[i] - locations[j]) <= k) {
                    f[i][k] = (f[i][k] + f[j][k - Math.abs(locations[i] - locations[j])]) % mod;
                }
            }
        }
    }
    return f[start][fuel];
}