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 | class Solution: |