Leetcode 1786. Number of Restricted Paths From First to Last Node

题目

解析

题目意思首先理解一下。就是说第一个节点和最后一个节点是1和n固定，返回符合要求的restricted path个数。这个restricted含义是，在path中离最后一个节点也就是n越远的节点，距离也必须越大。这里需要注意的是除了开始节点和结束节点固定之外，并没有要求path中的节点本身的数字必须要有顺序，只需要离最后一个节点的距离保持满足条件即可。所以解题分为两步：

通过最短路径算法找到每个节点离最后一个节点的最短距离，这里采用dijkstra找出符合条件的节点到最后节点距离降序的路径个数，这里采用dfs+memorization

另一点值得注意的是，其实这个第二步就是个top bottom的dp，但是这个题目却很难用我们熟悉的dp数组的方式来写，而必须采用这种recursion的方式。至于这个问题还没有想的特别清楚，可能的原因在于：除了开始节点和结束节点固定之外，并没有要求path中的节点本身的数字必须要有顺序，只需要离最后一个节点的距离保持满足条件即可。因为这个，所以没有办法很方便的提前建立子问题的关系，所以也不能很方便的找到便利节点的顺序，也就无法用那种常见的for循环dp，这个有待进一步考证

class Solution:def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:def dfs(node):if memo[node] != -1:return memo[node]ans = 0for nei,_ in g[node]:if dists[nei] < dists[node]:ans += dfs(nei)ans %= 1e9+7memo[node] = ansreturn memo[node]# build graphg = collections.defaultdict(list)for e in edges:g[e[0]].append([e[1],e[2]])g[e[1]]

如果觉得《Leetcode 1786. Number of Restricted Paths From First to Last Node》对你有帮助，请点赞、收藏，并留下你的观点哦！