输入(String[][] travel, String[][] point)
输出：int score
travel的形式是[["start","3","A],["A","4","B"],["B","5","END1"]]
point的形式为[["A","5"],["B","6"],["END","3"]]
代表到达每一个点的reward
Follow up 是要求打印从start到end的路径，就是使得score最大的那条路。
这题首先我们明确一点不能用Dijkstra方法做， 因为求的是最大值。
还有一点要注意到是这里面不可能有环，这是违反物理定律的。
这题可以有两种做法，一种是从上往下去做， 一种是backtracking从下往上返回。
从上往下去做的话要注意的一点是你要保证同一个点不会被expand两次。
比如 两条路径 A -> B -C , 从 A ->C。A 访问完之后不能立马访问C， 因为 还有一条边是从B-》C
必须要A，B都expand完了再expand。 所以这是很自然的引出来topologic order。
所以这题就是先建图，再按topological order BFS
第二种做法是从下往上back tracking。DFS。
我从A出发不知道哪条边能给我最好的结果，我就问一下子节点你们的最大值是多少，然后挑一个最大的。
为了避免重复计算， 当从一个点返回的时候把它存到map里面，下次直接取就好了。
这里帖一下DFS的解法。
public class Ski {
public int getMaxPath(String[][] travel, String[][] point) {
Map<String, Integer> pointMap = new HashMap<>();
Map<String, Map<String, Integer>> graph = new HashMap<>();
buildMap(travel, point, pointMap, graph);
Map<String, Integer> maxScore = new HashMap<>();
Map<String, String> nextMap = new HashMap<>();
dfsExplore("start", pointMap, graph, maxScore, nextMap);
System.out.println(printPath(nextMap, "start"));
System.out.println(maxScore);
return maxScore.get("start");
}
private int dfsExplore(String start, Map<String, Integer> pointMap,
Map<String, Map<String, Integer>> graph,
Map<String, Integer> maxScore,
Map<String, String> nextMap) {
if (maxScore.get(start) != null) return maxScore.get(start);
if (start.indexOf("end") == 0 || start.indexOf("END") == 0) {
maxScore.put(start, pointMap.get(start));
return maxScore.get(start);
}
int localMaxScore = Integer.MIN_VALUE;
Map<String, Integer> nextDes = graph.getOrDefault(start, new HashMap<>());
String next = "";
for (Map.Entry<String, Integer> entry : nextDes.entrySet()) {
int childScore = dfsExplore(entry.getKey(), pointMap, graph, maxScore, nextMap);
if (childScore == Integer.MIN_VALUE) continue;
int pathScore = childScore - entry.getValue();
if (pathScore > localMaxScore) {
localMaxScore = pathScore;
next = entry.getKey();
}
}
// add current score
if (localMaxScore != Integer.MIN_VALUE) {
localMaxScore += pointMap.get(start);
}
nextMap.put(start, next);
maxScore.put(start, localMaxScore);
return localMaxScore;
}
private void buildMap(String[][] travel, String[][] point,
Map<String, Integer> pointMap, Map<String, Map<String, Integer>> graph) {
for (String[] seg : travel) {
String st = seg[0], des = seg[1];
int cost = Integer.parseInt(seg[2]);
graph.putIfAbsent(st, new HashMap<>());
graph.putIfAbsent(des, new HashMap<>());
graph.get(st).put(des, cost);
}
for (String[] array : point) {
String city = array[0];
int score = Integer.parseInt(array[1]);
pointMap.put(city, score);
}
}
private String printPath(Map<String, String> nextPath, String start) {
String s = "start";
String ans = "";
while (s!= null && !s.equals("")) {
ans += s;
s = nextPath.get(s);
if (s != null && !s.equals("")) ans += "->";
}
return ans;
}
}
