传递信息

难度: Easy

小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：

有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0
每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。
每轮信息必须需要传递给另一个人，且信息可重复经过同一个人

给定总玩家数 n，以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。

示例 1：

输入：n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3

输出：3

解释：信息从小 A 编号 0 处开始，经 3 轮传递，到达编号 4。共有 3 种方案，分别是 0->2->0->4， 0->2->1->4， 0->2->3->4。

示例 2：

输入：n = 3, relation = [[0,2],[2,1]], k = 2

输出：0

解释：信息不能从小 A 处经过 2 轮传递到编号 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]

Submission

运行时间: 22 ms

内存: 16.0 MB

class Solution:
    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:
        dp = [[0]*(n+1) for _ in range(k+1)]
        # dp[i][j]: 经过i轮传递到编号j的玩家的方案数
        dp[0][0] = 1
        for i in range(k):
            for edge in relation:
                dp[i+1][edge[1]] += dp[i][edge[0]]
        return dp[k][n-1]

Explain

该题解采用动态规划的方式来解决传递信息的问题。动态规划数组 dp[i][j] 代表经过 i 轮传递到编号 j 的玩家的方案数。首先初始化 dp[0][0] = 1，表示从玩家 0 开始传递信息。然后对每一轮传递 i 从 0 到 k-1 进行遍历，更新 dp[i+1][j] 的值，即在第 i+1 轮传递到编号 j 的方案数，根据关系数组 relation 更新。relation 中的每一对 [src, dst] 表示信息可以从 src 传递到 dst。对于每一对 [src, dst]，当前轮 i 的 dp[i][src] 的值会加到下一轮 dp[i+1][dst] 上，表示经过 src 到达 dst 的所有可能的方案数。最终，dp[k][n-1] 就是问题的答案，即在第 k 轮传递到编号 n-1 的方案数。

时间复杂度: O(k * relation.length)

空间复杂度: O(k * n)

class Solution:
    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:
        # 初始化 dp 数组，大小为 (k+1) x (n+1)，全部初始化为 0
        dp = [[0]*(n+1) for _ in range(k+1)]
        # 初始化，从玩家0开始，所以第0轮传递到0的方案数为1
        dp[0][0] = 1
        # 遍历每一轮传递
        for i in range(k):
            # 遍历每一个传递关系
            for edge in relation:
                # 更新下一轮的方案数
                dp[i+1][edge[1]] += dp[i][edge[0]]
        # 返回第k轮传递到玩家 n-1 的方案数
        return dp[k][n-1]

Explore

这种更新方式基于状态转移的原理。在动态规划中，我们关注如何从已知的状态（即当前已经考虑的轮次和玩家）转移到下一个状态。这里 dp[i][src] 表示第 i 轮结束时，消息传递到玩家 src 的方案总数。当存在一条从 src 到 dst 的传递关系时，意味着在第 i+1 轮，玩家 src 可以将消息传递给玩家 dst。因此，我们将从 src 到 dst 的所有可能方案（即 dp[i][src]）累加到 dp[i+1][dst] 上，从而更新第 i+1 轮传递到 dst 的方案数。这种方法确保了所有通过不同路径到达 dst 的方案都被计算在内。

初始化 dp[0][0] 为 1 是因为传递信息的游戏从玩家 0 开始，所以在游戏开始时只有玩家 0 有消息。此时，消息尚未传递给其他玩家，因此，对于所有 j != 0，dp[0][j] 的值为 0，表示在游戏开始时，除了玩家 0 外，没有其他玩家接收到消息。这种初始化设置反映了问题的初始条件和约束。

如果 relation 数组为空，或者不存在从玩家 0 到玩家 n-1 的路径，这意味着在 dp 数组的更新过程中，从 dp[0][0] 开始的值无法被传递到任何其他玩家，特别是最终的目标玩家 n-1。无论进行多少轮传递（即 k 轮），dp[k][n-1] 的值将保持为 0，因为没有任何有效的传递路径可以使消息到达玩家 n-1。这反映了算法在处理无法完成任务的情况时的行为：输出将为 0，表示没有可行的方案数。