「这是我参与11月更文挑战的第20天,活动详情查看:2021最后一次更文挑战」
题目
小朋友 A 在和 ta 的小伙伴们玩传信息游戏,游戏规则如下:
- 有 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]
复制代码
解题思路
假设当前我们已经走了 i 步,所在位置为 j,那么剩余的 k - i 步,能否到达位置 n - 1,仅取决于「剩余步数 k - i」和「边权关系 relation」,而与我是如何到达位置 i 无关。
而对于方案数而言,如果已经走了 i 步,所在位置为 j,到达位置 n - 1 的方案数仅取决于「剩余步数 i - k」、「边权关系 relation」和「花费 i 步到达位置 j 的方案数」。
定义 f[i][j] 为当前已经走了 i 步,所在位置为 j 的方案数。
那么 f[k][n - 1] 为最终答案,f[0][0] = 1 为显而易见的初始化条件。
不失一般性的考虑,f[i][j] 该如何转移,f[i][j] 应该为所有能够到达位置 j 的点 p 的 f[i - 1][p] 的总和:
代码实现
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 = 0; i < k; i++) {
for (int[] edge : relation) {
int src = edge[0], dst = edge[1];
dp[i + 1][dst] += dp[i][src];
}
}
return dp[k][n - 1];
}
}
复制代码
最后
空间复杂度是: O(kn)
时间复杂度:O(km)O。其中 m 为 relation 数组的长度
**往期文章:
- 二叉树刷题总结:二叉搜索树的属性
- 二叉树总结:二叉树的属性
- 二叉树总结:二叉树的修改与构造
- StoreKit2 有这么香?嗯,我试过了,真香
- 看完这篇文章,再也不怕面试官问我如何构造二叉树啦!
- 那帮做游戏的又想让大家氪金,太坏了!
- 手把手带你撸一个网易云音乐首页 | 适配篇
- 手把手带你撸一个网易云音乐首页(三)
- 手把手带你撸一个网易云音乐首页(二)
- 手把手带你撸一个网易云音乐首页(一)
- 代码要写注释吗?写你就输了
- Codable发布这么久我就不学,摸鱼爽歪歪,哎~就是玩儿
- iOS 优雅的处理网络数据,你真的会吗?不如看看这篇
- UICollectionView 自定义布局!看这篇就够了
请你喝杯 ☕️ 点赞 + 关注哦~
- 阅读完记得给我点个赞哦,有👍 有动力
- 关注公众号--- HelloWorld杰少,第一时间推送新姿势
最后,创作不易,如果对大家有所帮助,希望大家点赞支持,有什么问题也可以在评论区里讨论😄~**
近期评论