Tag: parameter

I have been solving some algorithm questions recently and a pattern I have observed in some problems is as follows:

Given a string or a list, do an aggregation operation on each of its elements. Here in each of these elements we apply some recurrence to solve it.

An example of one such problem is below.

---

Problem: Given n integers return the total number of binary search trees that can be formed using the n integers

To solve this problem, I define a recurrence relation as follows:

f(n) = 1 // if n = 0 f(n) = ∑ f(i) * f(n-i-1) where 0 <= i <= n-1 

This works and I get the correct answer however I want to modify the function a bit.

Instead of expressing the function in terms of f(n) I want to express it in terms of f(n, i) so I can remove the summation. However I am unable to do it correctly.

---

Code

My code to solve the problem by defining the recurrence in terms of f(n) is as follows: (I am aware it can be optimized by DP but that is not what I am trying to do here)

public int f(int n) {     if(n == 0)         return 1;      int result = 0;     for(int i = 0; i< n; i++)         result += f(i) * f(n-i-1);     return result; } 

I want to remove that for loop and instead express the function in terms of f(n,i) instead of f(n).

---

Question

1. How to convert the recurrence shown above from f(n) to f(n,i) and remove the summation?
   • Here ‘n’ is the size of the list of element and ‘i’ is the ith element in the list that we choose to be the root of the tree.