小 A 和 ta 的小伙伴们玩传信息游戏,游戏规则如下:
有 n 名玩家,所有玩家编号分别为 0 ~ n-1,其中小朋友 A 的编号为 0
每个玩家都有固定的若干个可传信息的其他玩家(也可能没有)。传信息的关系是单向的(比如 A 可以向 B 传信息,但 B 不能向 A 传信息)。
每轮信息必须需要传递给另一个人,且信息可重复经过同一个人
给定总玩家数 n,以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数;若不能到达,返回 0。
写这个题是我在刷动态规划的时候遇到的一个题,但是我动态规划没有想到思路,仔细思考了一下,发现它可以使用搜索算法来做,所以我就尝试了一下用自己比较擅长的深度优先搜索来解答,果不其然有解。下面说下我的思路:
题目要求从起点0到终点n-1的可能路径总和,所以可以从0开始遍历,一直遍历直到终点,如果遍历不通,那就是没有路径可以到达。但题目还给了一个条件就是只能走k步,也就是说,即使你到达了终点,用了超过k步或者少于k步,这个路径也不可行。可以设置变量step,每走一步step++,一旦step等于k,这时候再判断终点是否为n-1,如果是,那么路径数+1,否则该条路径无解,直接结束。代码如下;
int ans = 0;
public int numWays(int n, int[][] relation, int k) {
for (int i=0;i<relation.length;i++){
if (relation[i][0] == 0) {
dfs(relation,relation[i][1],1,k,n);
}
}
return ans;
}
private void dfs(int[][] relation, int start, int step, int k,int n) {
if (step == k) {
if (start==n-1){
ans++;
}
return;
}
for (int i=0;i<relation.length;i++){
if (relation[i][0]==start){
dfs(relation,start,step+1,k,n);
}
}
}
动态规划解法参考了别人的:
public int numWaysWithDp(int n, int[][] relation, int k) {
int[][] dp = new int[k+1][n+1];
//从0-0只有一种方法
dp[0][0] = 1;
for(int i=1;i<=k;i++){
for (int j=1;j<=n;j++){
//第i轮到达玩家j的方案数,就是前一个玩家到达玩家j的方案之和
dp[i][relation[j][1]]+=dp[i-1][relation[j][0]];
}
}
return dp[k][n-1];
}