外企动态规划难题： Grouping Options

回溯暴搜，剪枝叶，只能过小规模数据

这时考虑dp了

dp[i][j] 表示前i个人分成j组的分法。
那么dp[i][i], i=1…n肯定是1。
对于dp[i][j]而言，我们可以把这j个组每个组分一个，那么剩下i-j个人，这i-j个人可以全部分配到最后1个组(对应dp[i-j][1])，也可以全部分配到最后2个组(对应dp[i-j][2])，…，也可以全部分配到全部的j个组(对应dp[i-j][j])。所以要用再用一个循环把这些方案都加起来就是dp[i][j]。

解法2：DP。时间复杂度O(m+n)。
思路是dp[i][j]可以分为2部分: 第1个数是1的和第1个数不是1的。
比如说n=8, m=4，那第1个数是1的情况就包括{1,1,1,5}, {1,1,2,4},{1,1,3,3},{1,2,2,3}，第1个数不是1的情况就是{2,2,2,2}。
那实际上
1）第1个数是1的情况就等价于dp[7][3]，即把第1个数拿掉后的情况，{1,1,5}, {1,2,4}, {1,3,3}, {2,2,3}。
2）第1个数不是1的情况就是将8分为4个数，但第1个数不是1的情况。等价于dp[4][4]，即因为每个元素都>1，所以每个元素减去1，然后求dp[4][4]即可。
怎么理解呢？比如说第2种情况是{2,3,4,5}，n=14，那么，我们可以给4个数每个数先分配一个1，剩下10在4个数里面分配，这就是dp[10][4]。

解法3：还是DP。
dp[i][j][k] 表示i拆除j个数，最后一个数是k有多少种方法
dp[i][j][k] = sum(dp[i - k][j - 1][x]), 1<=x<=k。
时间复杂度O(n^3 * m)，非常慢。
时间复杂度计算如下：i from 1 to n, j from 1 to m, k from 1 to n, x from 1 to k。
TBD