Given a number A, return number of ways you can draw A chords in a circle with 2 x A points such that no 2 chords intersect.
Two ways are different if there exists a chord which is present in one way and not in other.
Return the answer modulo 109 + 7.
Input Format:
The first and the only argument contains the integer A.
Output Format:
Return an integer answering the query as described in the problem statement.
Constraints:
1 <= A <= 1000
Examples:
Input 1:
A = 1
Output 1:
1
Explanation 1:
If points are numbered 1 to 2 in clockwise direction, then different ways to draw chords are:
{(1-2)} only.
So, we return 1.
Input 2:
A = 2
Output 2:
2
Explanation 2:
If points are numbered 1 to 4 in clockwise direction, then different ways to draw chords are:
{(1-2), (3-4)} and {(1-4), (2-3)}.
So, we return 2.
Method:
Everytime we connect two points, we are splitting the other points into two sets, and we can only connect points inside the two sets.
Solution:
Time: O(n^2) Space: O(n)
public class Solution { public int chordCnt(int A) { int n = 2 * A; long[] dp = new long[n + 1]; dp[0] = 1; dp[2] = 1; for (int i = 2; i <= A; i ++) { for (int j = 2; j <= 2 * i; j += 2) { dp[i * 2] += (dp[j - 2] * dp[2 * i - j]) % 1000000007; } dp[i * 2] = dp[i * 2] % 1000000007; // System.out.println(Arrays.toString(dp[n])); } return (int) dp[n]; } }