847. Shortest Path Visiting All Nodes
847. Shortest Path Visiting All Nodes
题目: https://leetcode.com/problems/shortest-path-visiting-all-nodes/
难度: Hard
题意：
- 给定一个图，问走遍所有的点的最短距离是多少
思路：
- 这个题首先考虑一下dfs的做法。假设我们已经到达了m个点，下个点，我们需要枚举所有下个点没有被访问的点，进行访问遍历，直到所有的点都被访问到
- 我们注意到，枚举的过程中，需要枚举所有下个点没有被访问的点，而这个跟先前访问的顺序无关，也就是状态是一个访问集合，和当前到达的点共同组合而成的
- 我们注意到，枚举的过程中，状态是需要重复访问，因此我们利用记忆化搜索，保存中间结果，进行动态规划
- 这里需要注意的，我们可以预先把图形中两两最短距离先求出来缓存起来，这一部分只需要o(n^3)的复杂度
- 子问题是：f(set, last)，set是访问集合，last是当前到达的点，函数值是达到当前状态最短距离
- 这里有个代码的实现方式，集合如何用实现？当然如果想实现一个具备集合特性的数据结构也是可以的，最简单的方式就是用bitset，也就是把集合的信息压缩在一个二进制串中，这个题的数据范围是n<=12，因此一个int就可以表达状态，状态总量是
2^n*n，因此这个动态规划的时间复杂度是o(2^n*n^2)
代码：
class Solution {
private int solve(int set, int last, int[][] dist, int[][] cache) {
if (cache[set][last] != -1) {
return cache[set][last];
}
if (set == (1 << dist.length) - 1) {
return cache[set][last] = 0;
}
int ret = 0x3fffffff;
for (int i = 0;i < dist.length;i++) {
if ((set & (1 << i)) == 0) {
ret = Math.min(ret, dist[last][i] + solve(set + (1 << i), i, dist, cache));
}
}
return cache[set][last] = ret;
}
private int[][] calDist(int[][] graph) {
int[][] dist = new int[graph.length][graph.length];
for (int i = 0;i < graph.length;i++) {
for (int j = 0;j < graph.length;j++) {
dist[i][j] = 0x3fffffff;
}
}
for (int i = 0;i < graph.length;i++) {
dist[i][i] = 0;
for (int j = 0;j < graph[i].length;j++) {
dist[i][graph[i][j]] = 1;
}
}
for (int k = 0;k < graph.length;k++) {
for (int i = 0;i < graph.length;i++) {
for (int j = 0;j < graph.length;j++) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
return dist;
}
public int shortestPathLength(int[][] graph) {
int[][] cache = new int[1 << graph.length][graph.length];
for (int i = 0;i < (1 << graph.length);i++) {
for (int j = 0;j < graph.length;j++) {
cache[i][j] = -1;
}
}
int[][] dist = calDist(graph);
int ret = 0x3fffffff;
for (int i = 0;i < graph.length;i++) {
ret = Math.min(ret, solve((1 << i), i, dist, cache));
}
return ret;
}
}
