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]