原文https://lwebapp.com/zh/post/leetcode-send-message
問題
小朋友 A 在和 他的小伙伴們玩?zhèn)餍畔⒂螒?，游戲?guī)則如下：
- 有
n名玩家，所有玩家編號分別為0 ～ n-1，其中小朋友A的編號為0 - 每個(gè)玩家都有固定的若干個(gè)可傳信息的其他玩家（也可能沒有）。傳信息的關(guān)系是單向的（比如
A可以向B傳信息，但B不能向A傳信息）。 - 每輪信息必須需要傳遞給另一個(gè)人，且信息可重復(fù)經(jīng)過同一個(gè)人
給定總玩家數(shù) n，以及按 [玩家編號,對應(yīng)可傳遞玩家編號] 關(guān)系組成的二維數(shù)組 relation。返回信息從小 A (編號 0 ) 經(jīng)過 k 輪傳遞到編號為 n-1 的小伙伴處的方案數(shù)；若不能到達(dá)，返回 0。
示例 1：
輸入：
n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3輸出：
3解釋：信息從小 A 編號 0 處開始，經(jīng) 3 輪傳遞，到達(dá)編號 4。共有 3 種方案，分別是 0->2->0->4， 0->2->1->4， 0->2->3->4。
示例 2：
輸入：
n = 3, relation = [[0,2],[2,1]], k = 2輸出：
0解釋：信息不能從小 A 處經(jīng)過 2 輪傳遞到編號 2
限制：
2 <= n <= 101 <= k <= 51 <= relation.length <= 90, 且 relation[i].length == 20 <= relation[i][0],relation[i][1] < n 且 relation[i][0] != relation[i][1]
解法一
思路：
深度優(yōu)先遍歷（DFS），從位置 0 開始遞歸查找下一個(gè)位置，每次遞歸查到指定步數(shù)停止，停止時(shí)候判斷目標(biāo)位置是否滿足要求，如果滿足要求就計(jì)數(shù)加 1。
代碼：
/**
* DFS
* @param {number} n
* @param {number[][]} relation
* @param {number} k
* @return {number}
*/
var numWays = function (n, relation, k) {
// 統(tǒng)計(jì)路徑數(shù)
let ways = 0;
const list = new Array(n).fill(0).map(() => new Array());
// 將一個(gè)開始位置對應(yīng)的多個(gè)傳遞位置搜集在一起，便于一起遍歷傳遞位置
for (const [from, to] of relation) {
list[from].push(to);
}
const dfs = (index, step) => {
// 當(dāng)步數(shù)達(dá)到指定k步時(shí)傳遞到了n-1位置即滿足要求
if (step === k) {
if (index === n - 1) {
ways++;
}
// 無論有沒有滿足要求，走了k步就可以停止了
return;
}
// 遞歸遍歷list的所有路徑
const targetList = list[index];
for (const nextIndex of targetList) {
dfs(nextIndex, step + 1);
}
};
// 第一步固定從1開始
dfs(0, 0);
return ways;
};
解法二
思路：
廣度優(yōu)先遍歷（BFS），構(gòu)造一個(gè)一維數(shù)組，將遍歷到第 k 步所有的結(jié)果存儲到這個(gè)數(shù)組中，最后再統(tǒng)計(jì)多少結(jié)果是滿足要求的。
代碼：
/**
BFS
* @param {number} n
* @param {number[][]} relation
* @param {number} k
* @return {number}
*/
var numWays = function (n, relation, k) {
const list = new Array(n).fill(0).map(() => new Array());
// 將一個(gè)開始位置對應(yīng)的多個(gè)傳遞位置搜集在一起，便于一起遍歷傳遞位置
for (const [from, to] of relation) {
list[from].push(to);
}
// 計(jì)步器
let step = 0;
// 從起始位置0開始
let queue = [0];
// 1. 沒有下一步目標(biāo)不需要遍歷
// 2. 步數(shù)到了k就不需要遍歷
while (queue.length && step < k) {
step++;
// 取得當(dāng)前queue的每一個(gè)位置，所對應(yīng)的所有下一個(gè)位置，也存儲進(jìn)queue，同時(shí)把當(dāng)前的每一個(gè)位置刪除，因?yàn)橐呀?jīng)走過了，這里是廣度優(yōu)先遍歷和深度優(yōu)先遍歷的區(qū)別之處
const length = queue.length;
for (let i = 0; i < length; i++) {
let index = queue.shift();
let targetList = list[index];
for (const nextIndex of targetList) {
queue.push(nextIndex);
}
}
}
// 統(tǒng)計(jì)路徑數(shù)
let ways = 0;
if (step === k) {
while (queue.length) {
if (queue.shift() === n - 1) {
ways++;
}
}
}
return ways;
};
解法三
思路：
動(dòng)態(tài)規(guī)劃（DP），構(gòu)造一個(gè)(k + 1) * n二維數(shù)組，將遍歷到第 k 步所有的結(jié)果的計(jì)數(shù)存儲到這個(gè)數(shù)組中，最后查看 k 步時(shí) n - 1 的位置的計(jì)數(shù)就是方案數(shù)。
比如
var n = 5,
relation = [
[0, 2],
[2, 1],
[3, 4],
[2, 3],
[1, 4],
[2, 0],
[0, 4],
],
k = 3;
構(gòu)造一個(gè) 4 * 5 的數(shù)組，從第0步開始，arr[0][0]計(jì)為 1
0: (5) [1, 0, 0, 0, 0]
1: (5) [0, 0, 0, 0, 0]
2: (5) [0, 0, 0, 0, 0]
3: (5) [0, 0, 0, 0, 0]
第一輪
0: (5) [1, 0, 0, 0, 0]
1: (5) [0, 0, 1, 0, 1]
2: (5) [0, 0, 0, 0, 0]
3: (5) [0, 0, 0, 0, 0]
第二輪
0: (5) [1, 0, 0, 0, 0]
1: (5) [0, 0, 1, 0, 1]
2: (5) [1, 1, 0, 1, 0]
3: (5) [0, 0, 0, 0, 0]
第三輪
0: (5) [1, 0, 0, 0, 0]
1: (5) [0, 0, 1, 0, 1]
2: (5) [1, 1, 0, 1, 0]
3: (5) [0, 0, 1, 0, 3]
最后得到 第三輪結(jié)束時(shí)候，達(dá)到n - 1的方案數(shù)為 3
代碼：
/**
* @param {number} n
* @param {number[][]} relation
* @param {number} k
* @return {number}
*/
var numWays = function (n, relation, k) {
const dp = new Array(k + 1).fill(0).map(() => new Array(n).fill(0));
dp[0][0] = 1;
for (let i = 0; i < k; i++) {
for (const [src, dst] of relation) {
dp[i + 1][dst] += dp[i][src];
}
}
return dp[k][n - 1];
};
更多l(xiāng)eetcode算法題解，leetcode 刷題筆記，經(jīng)典算法講解 https://lwebapp.com/zh/tag/leetcode
