leetcode：787. K 站中转内最便宜的航班【k步最短路 + dfs记忆化 + defaultdict(dict)】

ac code

class Solution:def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:# k站中转，可以走k + 1次connect = defaultdict(dict) # 二维dictfor x, y, c in flights:connect[x][y] = c# 只能走k步的dfs# 自顶向下@cachedef dfs(now, remain):# 成功退出if now == dst:return 0# 到达步数，无限远if remain == 0:return infremain -= 1res = inf# 遍历下一个位置for nxt in connect[now]:res = min(res, dfs(nxt, remain) + connect[now][nxt])return resans = dfs(src, k + 1)return ans if ans != inf else -1

分析

用一个defaultdict记录每一个点能飞到的地方和距离
自顶向下的dfs + cache
记忆化参数是当前的位置以及剩余的次数，结果是到达终点的距离
如果能到达终点，返回0
如果次数用尽，返回inf
次数-1，且当前res设置为inf
遍历所有能飞的下一个位置，然后res取res和dfs(nxt, remain) + connect[now][nxt]的最小值

这种思想就是把问题推到下一步，直到尽头（到达终点，次数用尽）

总结

dfs解决k步最短路问题，优雅