LeetCode LCP 07. 传递信息

约 4 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 字节
标签
动态规划 深度优先搜索 广度优先搜索 图 LCP

题目描述

✅ LCP 07. 传递信息

image-20260929105606689

image-20260929105606841

题意分析

信息从零号玩家出发，每轮必须沿一条给定的有向关系传给另一个人，允许重复经过同一玩家。统计恰好传递 k 轮后位于 n - 1 号玩家的路径数量。

关键是“恰好”，不是最多 k 轮。提前到达目标的路径还要继续传递，只有第 k 轮结束时重新或仍然位于目标，才算完成一次方案。

解法：按轮次 DP（滚动数组）

核心思路

[!blue]

dp[i] 表示当前已经完成的轮次下，信息停在玩家 i 手上的方案数。零轮时只有起点有一种方案，也就是尚未进行任何传递的初始状态，因此设置 dp[0] = 1，其他位置为零。

对一条关系 a -> b，每条当前到达 a 的路径都可以再传给 b，形成下一轮的一条路径，所以执行 next[b] += dp[a]。来自不同前驱的路径都要累加；每条新路径又有唯一的上一轮路径和最后一条关系，因此这样的转移不重不漏。

每轮新建全零的 next，所有转移只读取旧 dp。若原地累加，本轮刚到达某玩家的路径可能立即再走一条边，导致一轮传播多次；若把旧值复制进新数组，又相当于允许信息不传递而原地停留，两者都违反恰好增加一轮的要求。

遍历完所有关系后再令 dp = next，状态就从恰好 t 轮变成恰好 t + 1 轮。执行 k 次后，dp[n - 1] 就是答案。轮次数限制了路径长度，所以即使关系中有环也不会无限搜索，不能用全局访问标记禁止合法的重复经过。

解题步骤

  1. 初态只有零号玩家有一种方案。
  2. 每轮创建全零的新计数数组。
  3. 遍历有向边，将旧起点计数累加到新终点。
  4. 完成 k 轮后返回目标计数。

输入关系只允许指定方向的传递，不能自动补反向边。没有任何路径在某轮到达某玩家时，它在新数组中的计数保持零；到达没有出边的玩家后，这些路径下一轮无法继续，也会自然消失。目标不可在恰好 k 轮到达时，返回值就是零。

代码实现

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(n+k(n+E))$，E 为关系数，包含每轮数组清零。
  • 空间复杂度：$O(n)$，两层计数。

关键点总结

[!green]

  • 状态同时限定当前位置与已经传递的轮数。
  • 多条前驱路径要累加，不能覆盖。
  • 每条边只按输入方向传递。

易错点总结

[!yellow]

  • 在旧数组上直接累加：本轮新结果可能继续传播，变成一步走多条边。
  • 保留上一轮计数到下一轮：相当于增加题目没有允许的原地停留。
  • 提前到达目标就返回：没有满足恰好 k 轮。
  • 禁止重复经过节点：会漏掉经过环的合法路径。

相似题目

题目 难度 关联与区别
1575. 统计所有可行路径 困难 同样按有限资源记录有环路径，本题每轮代价1且必须恰好k轮，原题按距离消耗燃油并可少用。
787. K 站中转内最便宜的航班 中等 都要保留经过边数这一维，本题累计方案数，原题在步数限制内求最低费用。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/63379741
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！