一、题目

小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：

1. 有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0
2. 每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。
3. 每轮信息必须需要传递给另一个人，且信息可重复经过同一个人

给定总玩家数 n，以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。

点击查看原题
难度级别：简单（其实是中等级别）

二、思路

1）动态规划

由于最开始肯定从0出发，且需要看k步能够有多少条路径到n-1处。可以使用dp[i][j]表示第i轮到达j玩家的路径数量。那么有：

可以将数组压缩成一维

三、代码

1）动态规划

class Solution {
    public int numWays(int n, int[][] relation, int k) {
        int[][] dp = new int[k+1][n];
        dp[0][0] = 1;
        for (int i = 1; i <= k; i++) {
            for (int[] re : relation) {
                dp[i][re[1]] += dp[i-1][re[0]];
            }
        }
        return dp[k][n-1];
    }
}

时间复杂度为O(k*relation.length)，空间复杂度为O(kn)

优化

class Solution {
    public int numWays(int n, int[][] relation, int k) {
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i <= k; i++) {
            int[] temp = new int[n];
            for (int[] re : relation) {
                temp[re[1]] += dp[re[0]];
            }
            dp = temp;
        }
        return dp[n-1];
    }
}

时间复杂度为O(k*relation.length)，空间复杂度为O(n)