# Non-intersecting chords using Dynamic Programming (DP)

**Non-intersecting chords using Dynamic programming:** find number of ways in which N non- intersecting chords can be formed using these 2*N points.

Submitted by Ritik Aggarwal, on December 09, 2018

**Problem:** You are given N chord and 2*N points. You have to find the number of ways in which N non- intersecting chords can be formed using these 2*N points. The answer may be too large so the answer must be taken mod with 10^9 + 7.

**Constraints:** 1 <= N <= 100

**Example:**

Sample input 1: 2 Sample output 1: 2 Sample input 2: 100 Sample output 2: 558488487

**Explanation of the problem:**

In the first sample provided above, there are 2 chords and 4 points. Let us label them as A, B, C, D in order. Now possible arrangements are chords AB and chords CD, the second possible arrangement is chord AD and chord BC.

**Note:** we can’t take chord AC and chord BD because the will intersect and we only have to consider **non-intersecting chord**.

**Solution:**

Before proceeding to the solution we can see that the recursive solution will be hard to implement so we will proceed to the dynamic programming approach. In this approach, we select a point and a variable point and then make a chord using both points to divide the circle into two halves then using dp matrix we will find the number of ways to form rest of the chords in both halves multiply them and add them to the solution of **i ^{th}** column. We will proceed this with same fixed point and different variable point and store the answer in

**i**column.

^{th}**Algorithm:**

- Create dp matrix in which ith cell represent the number of ways to form ith points.
- Start filling dp matrix from the
**4**row (no need to fill odd columns as there answer will be zero).^{th} - Find the answer of each row by using dp relations.
- If points in any of the half is 0 then add the number of ways of another half in the answer.
- Otherwise, multiple numbers of ways in both the half and add to the answer of
**i**cell.^{th} - Store the answer in
**i**cell.^{th}

## C++ Code for Non-intersecting chords using Dynamic Programming (DP)

#include <iostream> using namespace std; long long int mod = 1000000007; // function to find the number of ways int non_intersecting(int n){ // total number of points is twice of n int tot_points = 2 * n; // Intializing all element to zero long long int dp[tot_points + 1] = {0}; // At 2 points number of ways in only 1 dp[2] = 1; for(int i = 4;i<tot_points + 1;i = i + 2){ long long int sum = 0; for(int j = 0;j<i;j = j + 2){ // number of points in first half int fh = j; // number of points in second half int sh = i - j - 2; // if there are 0 points in any half just // add number of ways of other half if(fh == 0){ sum += dp[sh]; sum %= mod; }else if(sh == 0){ sum += dp[fh]; sum %= mod; }else{ // used distributive property of modulus sum += ((dp[fh] * dp[sh]) % mod); sum %= mod; } } dp[i] = sum; } return dp[tot_points]; } // driver function int main() { int n; cin >> n; cout << n << endl; cout << non_intersecting(n); return 0; }

**Output**

2 2

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions