Problem Link:

http://codeforces.com/problemset/problem/455/D

The difficulty here is how to avoid double counting and how to store dp values.

The first observation we could made is that if we connect ** vertex i** and

**directly, the rest vertices are split into two parts, and vertices in each part can only connect to vertices in their own parts. This fact reminds us of the classical way of dynamic programming, i.e., the number of ways to connect vertices on a large interval is based on the number of ways to connect vertices on smaller intervals.**

*j*Next, how can we avoid double counting? We need to see some characteristics of the way of connecting the vertices on some interval. If we are to connect the vertices in the interval from ** l** to

**, i.e., connecting vertex**

*r***, and**

*l, l+1, …, r-1***, vertex l must directly connect to one or more of the vertices in the interval from**

*r***to**

*l+1***, since the all vertices must be connected. We can split the situation into different cases, each case in which the last vertex in the interval**

*r***connects to is different. Notice that if**

*vertex l***connects to**

*vertex l***in the interval, it does not follow that**

*vertex m***will not connect to any other vertices than**

*vertex l***, but what it really means is that all the other vertices that**

*vertex m***can connect to must come before**

*vertex l***in this interval. Then we can make the following claim: counting the ways of connecting vertices in the interval from different cases won’t count any distinct way of connecting the vertices more than once, and this is clear, as we have made the first observation. To handle the cases, we just need to calculate the ways of connecting vertices between**

*vertex m***and**

*vertex l***to**

*vertex m***or**

*vertex l***and the ways of connecting vertices between**

*vertex m***(inclusive) and**

*vertex m***(inclusive). The special case here is the case where we connect**

*vertex r***and**

*vertex l***directly, and we can handle this case by splitting the interval differently by iterating on the split point, and then connect the left part of the interval to**

*vertex r***and the right part of the interval to**

*vertex l***.**

*vertex r*The DP equations:

If we store the total number of ways of connecting vertices in interval from ** vertex l** to

**in**

*vertex r***, and the ways when**

*dp1[l][r]***and**

*vertex l***are directly connected in**

*vertex r***, we can write the following equations:**

*dp2[l][r]**dp2[l][r] = if(l and r can be connected) sum(dp1[l][m] * dp1[m+1][r]);*

*dp1[l][r] = sum(dp2[l][m] * dp1[m][r]);*

AC Code:

http://codeforces.com/contest/888/submission/35203999