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]].append([e[0],e[2]])# dikstra to label the distance of every node fron node nnodes = [[0,n]]dists = [float('inf')] * (n+1)dists[n] = 0while nodes:d, node = heapq.heappop(nodes)for nei,w in g[node]:if d+w < dists[nei]:new_d = d + wdists[nei] = new_dheapq.heappush(nodes,[new_d,nei])# print(dists)# dfs to find all satisfied pathsans = 0memo = [-1]*(n+1)memo[n] = 1return int(dfs(1) % (1e9+7))

时间复杂度：这边可以复习下dijkstra的时间复杂度计算
https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/tutorial/#:~:text=Time%20Complexity%20of%20Dijkstra’s%20Algorithm,E%20l%20o%20g%20V%20)%20.

在discussion里面找到一种很有趣的解法，没有特别看懂是啥意思，后面有空再研究研究
https://leetcode.com/problems/number-of-restricted-paths-from-first-to-last-node/discuss/1198567/Straightforward-Python-Dijkstra-%2B-DP-Beats-98-Runtime-and-Memory!

二刷c++

dijkstra+dfs with memorization

class Solution {
    
public:int helper(int node, int n, vector<int>& dists,vector<vector<pair<int,int>>>& g,vector<int>& visited, vector<int>& memo){
    if(node == n) return 1;if(memo[node] != -1) return memo[node];int res = 0;visited[node] = 1;for(auto& neigh : g[node]){
    int neigh_node = neigh.first;// int w = neigh.second;if(visited[neigh_node] == 0 && dists[neigh_node] < dists[node]){
    res += helper(neigh_node,n,dists,g,visited,memo);res = res % (1000000000+7);}}visited[node] = 0;memo[node] = res;return memo[node];}int countRestrictedPaths(int n, vector<vector<int>>& edges) {
    // dijkstra for shortest path of each node// build graphvector<vector<pair<int,int>>> g(n+1);for(auto& edge : edges){
    g[edge[0]].push_back(make_pair(edge[1],edge[2]));g[edge[1]].push_back(make_pair(edge[0],edge[2]));}priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;pq.push(make_pair(0,n));vector<int> dists(n+1,INT_MAX);dists[n] = 0;while(!pq.empty()){
    auto curr = pq.top();pq.pop();int dist = curr.first;int node = curr.second;// cout << node << endl;for(auto& neigh : g[node]){
    int neigh_node = neigh.first;int w = neigh.second;if(dist + w < dists[neigh_node]){
    pq.push(make_pair(dist + w, neigh_node));dists[neigh_node] = dist + w;}}}// for(auto& el : dists) cout << el << endl;vector<int> memo(n+1,-1);vector<int> visited(n+1,0);return helper(1,n,dists,g,visited,memo);}
};

看到了一种在dijkstra里面直接dp形成答案的，还是没有看懂是个什么原理，后面再说
https://leetcode.com/problems/number-of-restricted-paths-from-first-to-last-node/discuss/1097478/C%2B%2B-Dijkstra-%2B-DP