LeetCodeLCP07:传递信息

发表于 更新于 分类于 阅读次数： 本文字数： 454 阅读时长 ≈ 1 分钟

一、题目描述

二、示例

三、条件限制

四、解题思路及代码

记 $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]$ 即为方案总数。

1
2
3
4
5
6
7
8
9
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]