“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:

  1. There are n players, and the numbers of all players are 0 to N-1 respectively. Child A’s number is 0
  2. 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).
  3. 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 ~

  1. After reading, remember to give me a thumbs-up oh, there is 👍 power
  2. 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 😄 ~ **