LCP 07. 传递信息

Difficulty
easy
Tags
记忆化搜索
URL
https://leetcode.cn/problems/chuan-di-xin-xi/
Star
小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：
  1. 有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0
  1. 每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。
  1. 每轮信息必须需要传递给另一个人，且信息可重复经过同一个人
给定总玩家数 n，以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。
示例 1：
示例 2：
限制：
  • 2 <= n <= 10
  • 1 <= k <= 5
  • 1 <= relation.length <= 90, 且 relation[i].length == 2
  • 0 <= relation[i][0],relation[i][1] < n 且 relation[i][0] != relation[i][1]
通过次数46,652提交次数61,090

记忆化搜索

思路
典型的记忆化搜索，从 0 出发走k步到终点的路径数 = 0的所有邻接节点各自走k-1步到终点的路径数 之和，这就由当前问题推导出了子问题。所以可以用递归解决。
题解
class Solution:
    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:
        self.relation = self.build_graph(relation)
        return self.dfs(0, n-1, k)
        
    @cache
    def dfs(self, start, end, k):
        if k == 0:
            if start == end:
                return 1
            return 0

        res = 0
        for nxt  in self.relation[start]:
            res += self.dfs(nxt, end, k-1)

        return res


    def build_graph(self, relation):
        res = collections.defaultdict(set)
        for r in relation:
            res[r[0]].add(r[1])
        return res
题目说了可以多次重复，那如果不能重复的话，需要记录走过的路径，代码如下：
class Solution:
    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:
        relation = self.build_graph(relation)
        return self.dfs(0, n-1, relation, set(), k)
        
    
    def dfs(self, start, end, relation, path, k):
        if k == 0:
            if start == end:
                return 1
            return 0

        res = 0
        for nxt  in relation[start]:
            if (start, nxt) in path:
                continue
            path.add((start, nxt))
            res += self.dfs(nxt, end, relation, path, k-1)
            path.remove((start, nxt))

        return res


    def build_graph(self, relation):
        res = collections.defaultdict(set)
        for r in relation:
            res[r[0]].add(r[1])
        return res