🌕 LCP 07. 传递信息

难度: 🌕

问题描述

---

解法

class Solution {
    public int numWays(int n, int[][] relation, int k) {
        // 思路：
        // dp
        int[][] dp = new int[k + 1][n];
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        for(int[] arr: relation) {
            int from = arr[0];
            int to = arr[1];
            if(!map.containsKey(to)) {
                map.put(to, new ArrayList<Integer>());
            }
            ArrayList<Integer> list = map.get(to);
            list.add(from);
        }
        dp[0][0] = 1;
        // 进行 k 轮
        for(int i = 1; i <= k; i ++) {
            for(int j = 0; j < n; j ++) {
                // 找到 j 的上一个节点集合
                if(!map.containsKey(j)) {
                    continue;
                }
                ArrayList<Integer> list = map.get(j);
                for(int from: list) {
                    dp[i][j] += dp[i - 1][from];
                }
            }
        }
        return dp[k][n - 1];
    }
}

---

输出