“This is the 20th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”
The title
Kid A is playing A message game with his friends. The rules of the game are as follows:
- There are n players, and the numbers of all players are 0 to N-1 respectively. Child A’s number is 0
- Each player has a fixed number of other players to send messages to (or not). The relationship between messages is one-way (for example, A can send messages to B, but B cannot send messages to A).
- Each round the message must be passed to another person, and the message can pass through the same person repeatedly
Given the total number of players n, and the two-dimensional array relation formed according to the relation [player number, corresponding to transferable player number]. Return the number of schemes where the information is transferred from A (no. 0) to its partner (no. N-1) through k rounds; If not, return 0.
Example 1:
Input: n = 5, base = [[0, 2], [2, 1], [3, 4], [2, 3], [1, 4], [2, 0], [0, 4]], k = 3 output: 3: information from A number of the zero beginning, through three rounds, to no. 4. There are 3 options, namely 0->2->0->4, 0->2->1->4, 0->2->3->4.Copy the code
Example 2:
Input: n = 3, relation = [[0,2],[2,1]], k = 2 Output: 0 Explanation: Information cannot be passed from small A to number 2 through 2 roundsCopy the code
Limitations:
2 <= n <= 10 1 <= k <= 5 1 <= relation.length <= 90, Relation [I]. Length == 2 0 <= relation[I][0],relation[I][1] < n and relation[I][0]! = relation[i][1]Copy the code
Their thinking
Suppose that we have taken I steps at position J, then whether the remaining k-i steps can reach position n-1 depends only on “the number of remaining steps k-i” and “relation of edge weight”, and has nothing to do with how I reach position I.
As for the number of schemes, if I steps have been taken and the position is J, the number of schemes reaching position n-1 only depends on “the number of remaining steps i-k”, “relation of edge weight” and “the number of schemes taking I steps to reach position J”.
Define f[I][j] as the number of schemes that have taken I steps and are at position J.
Then f[k][n-1] is the final answer, and f[0][0] = 1 is the obvious initialization condition.
Without loss of generality, how f[I][j] should be transferred, f[I][j] should be the sum of f[i-1][p] of all points p that can reach position J:
Code implementation
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]; }}Copy the code
The last
The space complexity is O(KN).
Time complexity: O(km)O. Where M is the length of relation array
Previous articles:
- Binary tree brush summary: binary search tree properties
- Binary tree summary: binary tree properties
- Binary tree summary: binary tree modification and construction
- StoreKit2 smells this good? Yeah, I tried it. It smells good
- After reading this article, I am no longer afraid of being asked how to construct a binary tree.
- The game guys are trying to get people to pay again. That’s bad!
- Take you rolled a netease holding cloud music home | adapter
- Netease Cloud Music Home Page (3)
- Netease Cloud Music Home Page (2)
- Netease Cloud Music Home Page (a)
- Does the code need comments? Write and you lose
- I would not study in Codable for a long time. They are for fun
- IOS handles web data gracefully. Do you really? Why don’t you read this one
- UICollectionView custom layout! This one is enough
Please drink a cup ☕️ + attention oh ~
- After reading, remember to give me a thumbs-up oh, there is 👍 power
- Follow the public number – HelloWorld Jie Shao, the first time push new posture
Finally, creation is not easy, if it is helpful to you, I hope you can praise and support, what questions can also be discussed in the comments section 😄 ~ **