LeetCode LCP 07. 传递信息
目录
题目描述
题意分析
n个玩家编号0到n-1，relation给出若干条单向传递关系：[a, b]表示a可以把信息传给b。信息从0号玩家出发，恰好经过k轮传递，问最终传到n-1号玩家手上的方案数有多少种。三个词必须读准。第一，单向——
[a, b]不代表b能传给a，建图时不能加反向边。第二，恰好k轮，不是「不超过k轮」；即使第 3 轮就到了n-1，只要k是 5，这条路径也不算数，除非它能继续绕出去再回来凑满 5 轮。第三，求的是方案数而不是可达性或最短路，所以要累加计数而不是取最值或布尔或。「恰好走
k步」是最强的算法信号。它意味着状态里必须带上步数这一维——同一个玩家在第 2 轮和第 3 轮拿到信息是完全不同的状态，不能合并。这也解释了为什么不能用最短路或并查集：那些结构会把「几步到达」的信息抹掉。约束里
n <= 10、k <= 5、relation长度不超过 90。规模极小，$O(k \cdot E)$ 只有几百次运算，甚至朴素 DFS 枚举所有路径也能过。规模小说明这题考的是状态设计的准确性——尤其是「恰好」这个约束怎么落到代码里。边界方面：可能一条路径都没有，答案为 0；
n-1号玩家在中途被经过是允许的，只要最后一轮结束时停在它身上即可；玩家可以在环上来回传递（题目没禁止重复经过同一玩家），所以不能用访问标记去重。
解法：按轮次 DP（滚动数组）
核心思路
最直接的想法是 DFS：从 0 出发，每层沿所有出边往下走，走满
k层时检查是否停在n-1。这在本题规模下能过，但它把同一状态重复计算了很多次——不同的前缀路径只要在第t轮落到同一个玩家身上，后续的走法与计数就完全相同，却被独立地重跑了一遍。这个观察正是 DP 的切入点：后续方案数只取决于「当前在谁手上」和「还剩几轮」，与之前怎么走过来的无关。于是把「路径」这个庞大的对象压缩成「(玩家, 轮次)」二元状态。
定义状态：
dp[t][i]表示信息经过恰好t轮传递后停在玩家i手上的方案数。初始状态是
dp[0][0] = 1、其余为 0——第 0 轮（一次都没传）时信息在 0 号手上，方案数是 1；其他玩家在第 0 轮不可能持有信息，所以是 0，而不是「未定义」。这个初值是整个递推的地基。转移：对每条边
[a, b]，第t轮停在a的每一种方案，都能通过这条边延伸成第t+1轮停在b的一种方案，因此
dp[t+1][b] += dp[t][a]遍历所有边做一遍，就完成了从第
t轮到第t+1轮的整体转移。答案是dp[k][n-1]。维持的不变量是：每一轮转移结束后，
dp中每个位置的值都恰好等于「从 0 号出发、恰好走了当前轮数、停在该玩家」的路径条数。加法对应「路径的并」——到达b的所有方案按最后一步走的是哪条边分类，各类互不相交且穷尽，所以直接求和不重不漏。由于第
t+1轮只依赖第t轮，二维数组可以压成两个一维数组滚动。这里必须用一个全新的next数组而不是在dp上原地累加：如果原地做，本轮刚写入next[b]的值可能在同一轮里又被当作dp[b]用于转移，等于一步走了多次，轮次的语义彻底崩坏。新建数组同时还免费提供了「未被任何边到达的玩家自动归零」这一效果——这正是「恰好k轮」的关键：上一轮的残留值不会被带进下一轮。最后强调为什么这个模型天然满足「恰好」：每一轮都强制走一条边，没有「原地停留」的转移，所以走完
k轮的路径长度必然恰好是k。若题目改成「不超过k轮」，就要额外加一条自环式的保留转移，或者把各轮答案累加。
解题步骤
- 初始化
dp为长度n的全零数组，令dp[0] = 1：语义是「第 0 轮时各玩家持有信息的方案数」。为什么dp[0] = 1而不是 0：信息初始就在 0 号手上，这算一种「什么都还没做」的方案，它是所有路径的公共起点。- 外层循环
k次：每一轮代表一次传递。为什么用for step = 0; step < k; step++而不是从 1 计数：只关心执行次数，两种写法等价，但要确保总共恰好执行k次转移。- 每轮新建
next数组（全零）：为什么必须新建：一是避免同一轮内的连锁转移（信息一步走成多步）；二是让「本轮无人到达的玩家」自动为 0，从而保证轮次语义严格。- 遍历所有边做转移：对每条
[a, b]执行next[b] += dp[a]。为什么是累加而不是赋值：同一个b可能有多条入边，来自不同前驱的方案要全部加起来。为什么是dp[a]而不是next[a]：转移的来源必须是上一轮的状态。- 为什么遍历边而不是遍历点对：
relation直接给的就是边列表，逐边转移最省事，也自然处理了「无边则不转移」的情况；若先建邻接矩阵再用双层循环遍历点对，反而多一步且在稀疏图上更慢。- 滚动替换：
dp = next，进入下一轮。- 返回
dp[n-1]：k轮转移全部结束后，dp的语义正是「恰好k轮后各玩家的方案数」，取n-1即答案。以
n = 5、relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]]、k = 3走一遍（预期答案 3）。
初始：dp = [1, 0, 0, 0, 0]。
第 1 轮：新建next = [0,0,0,0,0]。逐边处理——[0,2]让next[2] += dp[0] = 1；[2,1]让next[1] += dp[2] = 0；[3,4]加 0；[2,3]加 0；[1,4]加 0；[2,0]加 0；[0,4]让next[4] += dp[0] = 1。得dp = [0, 0, 1, 0, 1]。含义是一轮后信息可能在 2 号或 4 号手上，各 1 种走法。
第 2 轮：新建next。[0,2]加dp[0] = 0；[2,1]让next[1] += dp[2] = 1；[3,4]加dp[3] = 0；[2,3]让next[3] += 1；[1,4]加dp[1] = 0；[2,0]让next[0] += 1；[0,4]加 0。得dp = [1, 1, 0, 1, 0]。注意第 1 轮时dp[4]的那个 1 在这里没有任何出边可走（4 号不是任何边的起点），于是自然消失——这正是新建数组带来的正确行为，若原地累加它会残留下来被错误计入。
第 3 轮：新建next。[0,2]让next[2] += dp[0] = 1；[2,1]加dp[2] = 0；[3,4]让next[4] += dp[3] = 1；[2,3]加 0；[1,4]让next[4] += dp[1] = 1，累计为 2；[2,0]加 0；[0,4]让next[4] += dp[0] = 1，累计为 3。得dp = [0, 0, 1, 0, 3]。
返回dp[4] = 3，与预期一致。三条路径分别是0→2→0→4、0→2→1→4、0→2→3→4。再看无解用例
n = 3、relation = [[0,2],[2,1]]、k = 2：初始dp = [1,0,0]；第 1 轮得[0,0,1]；第 2 轮[2,1]让next[1] += 1，得[0,1,0]。返回dp[2] = 0，正确——两轮后信息在 1 号手上而不是 2 号。
代码实现
class Solution {
public int numWays(int n, int[][] relation, int k) {
// dp[i] = 当前轮次下，信息停在玩家 i 手上的方案数。
int[] dp = new int[n];
dp[0] = 1;
for (int step = 0; step < k; step++) {
// 新建数组：既避免一轮内连锁转移，也让无人到达的玩家自动归零。
int[] next = new int[n];
for (int[] e : relation) {
next[e[1]] += dp[e[0]];
}
dp = next;
}
return dp[n - 1];
}
}
func numWays(n int, relation [][]int, k int) int {
// dp[i] = 当前轮次下，信息停在玩家 i 手上的方案数。
dp := make([]int, n)
dp[0] = 1
for step := 0; step < k; step++ {
// 新建切片：既避免一轮内连锁转移，也让无人到达的玩家自动归零。
next := make([]int, n)
for _, e := range relation {
next[e[1]] += dp[e[0]]
}
dp = next
}
return dp[n-1]
}
复杂度分析
- 时间复杂度：$O(k \cdot E)$，其中
E是relation的长度。凭什么：外层恰好k轮，每轮遍历全部边一次，每条边只做一次加法；新建数组的开销是 $O(n)$，被 $O(E)$ 吸收（有边可走时E >= 1）。代入约束是 $5 \times 90 = 450$ 次运算。- 空间复杂度：$O(n)$。凭什么：任意时刻只同时存在
dp与next两个长度为n的数组，旧的一份在滚动后即可回收；没有按轮次保存k层状态，也没有额外建邻接表。
关键点总结
- 「恰好走
k步」必须把步数写进状态维度。凡是题面出现「恰好」「正好」「第 k 次」，都要先确认状态里有没有这一维，否则不同步数的方案会被错误合并。- 路径计数题的通用降维思路是：后续走法只依赖「当前位置 + 剩余步数」，与前缀路径无关，因此可以把指数级的路径集合压缩成多项式级的状态表。
- 计数用加法、可达性用或、最优化用取最值——三者的转移骨架完全相同，区别只在合并算子。看清题目要哪一种，再套同一个模板。
- 滚动数组必须新建而不能原地累加，否则同一轮内会发生连锁转移。新建还顺带保证了「上一轮的残留不会被带入」，这对「恰好 k 步」的语义至关重要。
- 逐边转移（而不是逐点对枚举）在稀疏图上更省，也天然跳过不存在的边；边列表本身就是最方便的输入形式。
- 面试视角：先说朴素 DFS 会重复计算相同的「(位置, 轮次)」状态，再给出
dp[t][i]的完整定义，最后解释滚动为什么要新建数组。状态定义那句话是得分点；若被追问优化，可以提「把relation转成n × n的邻接矩阵后，k轮转移等价于矩阵的k次幂，用快速幂可以把复杂度降到 $O(n^3 \log k)$」，这在k极大时才有意义。
易错点总结
- 错误写法：在
dp上原地累加而不新建next→ 用例relation = [[0,1],[1,2]]、k = 1中一轮内信息从 0 连锁走到 2，dp[2]被错误置 1，而一轮只能走一步。- 错误写法：
next复用同一个数组但只清零一次 → 用例n = 5、k = 3中第 1 轮停在 4 号的那份方案残留到后续轮次，答案被虚增。- 错误写法：把边当成双向，同时执行
next[e[1]] += dp[e[0]]与next[e[0]] += dp[e[1]]→ 用例relation = [[0,2],[2,1]]、k = 2中出现0→2→0这类反向走法，答案偏大。- 错误写法：初始化写成
dp[0] = 0或整体全 0 → 所有轮次的转移都从 0 开始累加，任何用例都返回 0。- 错误写法：初始化时把所有玩家都设成 1 → 用例中信息可以从任意玩家出发，答案严重偏大；起点唯一是题目明确给出的条件。
- 错误写法：外层循环写成
for step = 1; step <= k; step++但内部又多做了一次初始转移 → 实际执行k + 1轮，用例k = 3的答案变成 4 轮的结果。- 错误写法：中途发现
dp[n-1] > 0就提前返回 → 用例relation含[0,4]、k = 3中第 1 轮就能到 4 号，提前返回得 1，而正确答案是 3（必须恰好 3 轮）。- 错误写法：用 DFS 且加访问标记防止重复经过同一玩家 → 用例中
0→2→0→4这条合法路径重复经过了 0 号，被访问标记挡住，答案从 3 降到 2。- 错误写法：用 BFS 求最短路后判断步数是否等于
k→ 用例中最短路只有 1 步，无法回答「恰好 3 步有几种走法」，模型根本不匹配计数需求。- 错误写法：转移写成
next[e[1]] = dp[e[0]]（赋值而非累加） → 用例k = 3的最后一轮里 4 号有三条入边，后写的覆盖先写的，答案从 3 变成 1。- 错误写法：转移来源误取
next[e[0]]→ 用例中读到的是本轮尚未写完的值，结果依赖relation中边的排列顺序，同一输入换个边序答案就变。- 错误写法：返回
dp[0]或忘记n - 1的下标 → 用例中返回的是信息回到起点的方案数，与题意不符。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 576. 出界的路径数 | 中等 | 同为「恰好/至多 k 步」的路径计数，但状态在网格上且要处理越界即计数 |
| 688. 骑士在棋盘上的概率 | 中等 | 步数维度相同，但转移带概率权重，答案是浮点数而非整数计数 |
| 787. K 站中转内最便宜的航班 | 中等 | 同样按轮次滚动且必须新建数组，但合并算子是取最小值而不是求和 |
| 62. 不同路径 | 中等 | 路径计数的入门形态，步数由网格坐标隐含决定，无需单独的轮次维度 |
| 70. 爬楼梯 | 简单 | 一维步数计数，展示「方案数用加法合并」这一骨架的最简形式 |
| 797. 所有可能的路径 | 中等 | 需要列举路径本身而非计数，只能回溯，无法压缩成状态表 |
| 743. 网络延迟时间 | 中等 | 同为有向图上的传播问题，但求的是最短到达时间，用 Dijkstra 而非计数 DP |