LeetCodeLCP07:传递信息

发表于 更新于 分类于 阅读次数： 本文字数： 485 阅读时长 ≈ 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]