本文主要是介绍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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
