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

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]