Goku and Dragon Balls

From the given conditions it is clear that we have to find how many structurally unique binary search trees are possible.

To find the unique BSTs,  we define two functions:

A(i,N): It denotes the number of unique BSTs, with ‘i’ (1 <= ‘i’ <= N) as the root.

B(N): It denotes the number of unique BSTs for a sequence of length N (number of Dragon Balls).

Now, we construct B(N) by the sum of A(i, N) :

B(N) = A(1, N) + A(2, N) + … + A(N, N)

Notice that when we select ‘i’ as a root i.e. A(i, N), we have i - 1 nodes which can be used to form a left subtree and n - 1 nodes to form a right subtree.

A(i, N) = B(i - 1) * B(N - i)

Thus, A(i, N) can be calculated by the product of the number of unique BSTs with i - 1 nodes and the number of unique BSTs with N - i nodes. Uniqueness is guaranteed by the sizes of the left subtree and the right subtree.

Here is the algorithm :

• If N is 0 or 1 then we return 1 because the number of unique BSTs with 0 nodes or 1 node is 1.
• We initialize ‘sum’ to 0. ‘sum’ stores gokuAndDragonBalls(N).
  • We iterate form i = 1 to i = N and call the recursive function.
  • We update sum as sum += gokuAndDragonBalls(i - 1) * gokuAndDragonBalls(n - i).
• Finally, we return the sum as our answer.

If we draw the recursion tree for the recurrence relation of approach 1, we can observe that there are a lot of overlapping subproblems. 

Since the problem has overlapping subproblems, we can solve it more efficiently using memorization. 

We take an extra array ‘memo’ of size N to store previously calculated results. We use here the same recurrence relation of the previous approach with the ‘memo’ array.

Algorithm:

The algorithm is similar to the previous approach with some additions. 

We initialize a memo[n+1] array with -1. memo[i] will store the number of different unique BSTs having the number of Dragon balls as ‘i’.

Before calling the function for any valid gokuAndDragonBalls(i), we will check whether we already have a solution corresponding to the gokuAndDragonBalls(i) present in memo. 

• If we already have a solution corresponding to gokuAndDragonBalls(i), we return that solution i.e memo[i].
• Else we initialise ‘sum’ to 0 to store gokuAndDragonBalls(i).
• We iterate from i = 1 to i = N and call the recursive function.
  • sum += gokuAndDragonBalls(i - 1) * gokuAndDragonBalls(n - i)
• We then set memo[i] to sum and return memo[i] as our answer.

Initially, we were breaking a large problem into smaller subproblems but now, let us look at it differently. The idea is to solve the small problem first and then reach the final answer. Thus we will be using a bottom-up approach now. 

Algorithm:

Let’s define a function gokuAndDragonBalls(N), where N is the number of Dragon Balls

• We initialize a dp[N+1] array with 0. dp[i] will store the number of different unique BSTs having  ‘i’ number of Dragon balls.
• We initialise dp[0] = 1 and dp[1] = 1 as the number of unique BSTs with 0 nodes or 1 node is 1 (base case).
• Now, we iterate form i = 2 to i = N.
  • sum = 0
  • Iterate ‘k’ from 1 to i:
    • sum = sum + dp[ k - 1 ] * dp[ i - k ]
    • dp[i] = sum
• Finally, we return dp[n] as answer.