LeetCodeLCP07:传递信息

一、题目描述

二、示例

三、条件限制

四、解题思路及代码

记 $dp[i][j]$ 为经过第 $i$ 轮传递到编号 $j$ 的玩家的方案数。

对于传信息的关系 $[from_, to_]$，如果第 $i$ 轮传递到编号 $from_$ 的玩家，则第 $i+1$ 轮可以从编号 $from_$ 的玩家传递到编号 $to_$ 的玩家。因此在计算 $dp[i+1][to_]$ 时，需要考虑可以传递到编号 $to_$ 的所有玩家，即：

$$dp[i+1][to\_] = \sum dp[i][from\_]$$

最终，$dp[k][n-1]$ 即为方案总数。

class Solution:
    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:
        dp = [[0]*(n+1) for i in range(k+1)]
        dp[0][0] = 1
        for i in range(k):
            for re in relation:
                from_, to_ = re
                dp[i+1][to_] += dp[i][from_]
        return dp[k][n-1]