求一个算法，多边形对角线的问题

[plan9]

问题是这样的

有一个多边形，有n个顶点，现在想取m个对角线，而行这m个对角线是不相交的，问最多有多少种取法

比如，5个顶点的多边形，取2个不相交的对角线，可以有5种取法

做interviewstreet的编程挑战，卡到这里了，求解惑

[darkgt]

见过类似的问题，参见http://discuss.codechef.com/questions/1968/maxgame-editorial
不过那个问题没有限制对角线的个数(m)，而且K=1的时候是要求对角线不能共点。
@zellux说的会导致重复情况被算了多次，不过做法类似。
放对角线的过程可以看做：
给一个n个点多边形形状的蛋糕，然后每次沿着2个顶点切一刀，(这两块蛋糕有一块只有1个刀痕，另一块有2个刀痕)，留下那个有1个刀痕的，重复上面的过程。
有个问题是重复计算，比如(0,1,2,3,4,5)的一个方案是(0,4)(0,3)(1,3)，先切(0,4)或(1,3)都会产生这个结果。不过还好，这种对于每种方案，只重复了2次(这里需要一些抽象思维)，因为切蛋糕的顺序只能是(0,4)(0,3)(1,3)或者(1,3)(0,3)(0,4)，两种方案是顺序反过来的。

下面说做法:
首先考虑在一个n点多边形(蛋糕^^)放一条对角线，会把多边形分成 i个点 和 n-i+2个点的两个多边形(稍微比划一下就能想出来)，只在i个点那个多边形里继续操作，然后将最后的合法方案数/2。
递归是非常慢的，实现上使用动态规划就可以了。
dp[n][m]表示在个n点多边形放m个对角线的方案数，dp[n][m] = sum( dp[i][m-1] )，i=3~n-i-1
两个循环即可，复杂度O(n*n*m)

[darkgt]

更正一下。
计数那里有点问题，在一个有n个边的蛋糕切一刀，保留有i条边的子蛋糕(并且只有1个切痕)，这个过程的方案刚才忘考虑了。
我想了下，应该是n-i+1

所以 dp[n][m] = sum( dp[i][m-1]*(n-i+1) )