小朋友 A 在和 他的小伙伴们玩传信息游戏，游戏规则如下：
有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0
每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，
但 B 不能向 A 传信息）。每轮信息必须需要传递给另一个人，且信息可重复经过同一个人，给定总玩家数 n，
以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。
返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。
示例 1：
输入：n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3
输出：3
解释：信息从小 A 编号 0 处开始，经 3 轮传递，到达编号 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 处经过 2 轮传递到编号 2
限制：
2 <= n <= 10
1 <= k <= 5
1 <= relation.length <= 90, 且 relation[i].length == 2
0 <= relation[i][0],relation[i][1] < n 且 relation[i][0] != relation[i][1]
自我解答
输入的 relation 其实是表示图的 边集数组, 于是想到可以使用深度优先遍历的方式，
不过这里和图遍历不一样的是，单个结点可以访问多次。
因此，使用字典来记录下每个结点的邻接点, 在深度优先遍历记录 方案数
class Solution5:
def numWays(self, n: int, relation: List[int], k: int) -> int:
from collections import defaultdict
relation_map = defaultdict(list)
for s, e in relation:
relation_map[s].append(e)
def _send(i, r=0):
if r == k:
return 1 if i == n - 1 else 0
if i not in relation_map:
return 0
ways = 0
nexts = relation_map[i]
for ne in nexts:
ways += _send(ne, r + 1)
return ways
ways = _send(0)
return ways
题解(动态规划)
我并没有想到使用动态规划，因为这是求所有的方案数，似乎并不是求最优解，所有怎么去刻画最优子结构呢？
而且在图里面，要找到所有的可行方案，不得每条路都去尝试吗？似乎没有办法省略操作呢。
刻画最优子结构
我忽略了 k轮这个变量，假设最后一个人的编号为 y
那么最优解问题可描述为："从 0 开始，经过 k 轮 到 y 的 最大方案数", 记作 f(k, y)
假设 x1, x2 经过一轮能到达 y，则说明最优解等于下列方案数的和：
"从 0 开始，经过 k - 1 轮 到 x1 的 最大方案数"
"从 0 开始，经过 k - 1 轮 到 x2 的 最大方案数"
公式可以描述为 f(k, y) = sum(f(k-1, x1), f(k1, x2))
带备忘的自顶向下法
实际上，就是 “深度优先” + 缓存
class Solution6:
def numWays(self, n: int, relation: List[int], k: int) -> int:
from collections import defaultdict
relation_map = defaultdict(list)
for s, e in relation:
relation_map[s].append(e)
def _send(i, r=0):
if (i, r) in dp:
return dp[(i, r)]
if r == k:
return 1 if i == n - 1 else 0
if i not in relation_map:
return 0
ways = 0
nexts = relation_map[i]
for ne in nexts:
ways += _send(ne, r + 1)
dp[(i, r)] = ways
return ways
dp = {}
ways = _send(0)
return ways
自底向上法
这个方法是需要从最小的子问题开始，一路向上。我自己没想出来，最小子问题就是 0 至下一个
的方案数分别是 1， 可以 “下一个” 有很多个，要确定这个方案数似乎还是得遍历图，尝试后发现
只是把上面得反过来写了，本质是一样的。
力扣题解做法不在图遍历框架里，
1、设置二维数组 dp， dp[k][y] 表示从 0 开始 经过 k 轮 到 y 的方案数。
2、我们知道公式：dp(k, y) = sum(dp(k-1, x1), dp(k1, x2)),
其中，x1, x2, 是需要从 relation 获取的，relation 中会存在 (x1, y), (x2, y)
3、最小的子问题是 “从 0 经过 1 轮的方案数都为 1 ”，假设 relatioin 中 有 (0, x3), (0, x4)
则 dp[1][x3] = 1, dp[1][x4] = 1
class Solution7:
def numWays(self, n: int, relation: List[int], k: int) -> int:
dp1 = [0 for x in range(n)]
dp1[0] = 1
for i in range(k):
dp2 = [0 for x in range(n)]
for x, y in relation:
dp2[y] += dp1[x]
dp1 = dp2
return dp1[n-1]