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 j 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.

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 r, i.e., connecting vertex l, l+1, …, r-1, and r, vertex l must directly connect to one or more of the vertices in the interval from l+1 to r, 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 vertex l connects to is different. Notice that if vertex l connects to vertex m in the interval, it does not follow that vertex l will not connect to any other vertices than vertex m, but what it really means is that all the other vertices that vertex l can connect to must come before vertex m 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 l and vertex m to vertex l or vertex m and the ways of connecting vertices between vertex m (inclusive) and vertex r (inclusive). The special case here is the case where we connect vertex l and vertex r 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 l and the right part of the interval to vertex r.

The DP equations:

If we store the total number of ways of connecting vertices in interval from vertex l to vertex r in dp1[l][r], and the ways when vertex l and vertex r are directly connected in dp2[l][r], we can write the following equations:

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