纠结了很久的整数划分，终于搞懂了，做笔记做笔记！！！
首先是问题描述与常见文字描述：
【问题求解】设n=5，k=5，对应的拆分方案有：
① 5=5
② 5=4+1
③ 5=3+2
④ 5=3+1+1
⑤ 5=2+2+1
⑥ 5=1+1+1+1
⑦ 5=1+1+1+1+1?
为了防止重复计数，让拆分数保持从大到小排序。正整数5的拆分数为7。
采用动态规划求解整数拆分问题。设f(n，k)为n的k拆分的拆分方案个数：
（1）当n=1，k=1时，显然f(n，k)=1。 ? ?
（2）当n<k时，有f(n，k)=f(n，n)。 ? ?
（3）当n=k时，其拆分方案有将正整数n无序拆分成最大数为n-1的拆分方案，以及将n拆分成1个n（n=n）的拆分方案，后者仅仅一种，所以有f(n，n)=f(n，n-1)+1。
（4）当n>k时，根据拆分方案中是否包含k，可以分为两种情况： ? ? ?
? ? ?① 拆分中包含k的情况：即一部分为单个k，另外一部分为{x1，x2，…，xi}，后者的和为n-k，? ? ?后者中可能再次出现k，因此是（n-k）的k拆分，所以这种拆分方案个数为f(n-k，k)。
? ? ?
?
? ? ?② 拆分中不包含k的情况：则拆分中所有拆分数都比k小，即n的（k-1）拆分，拆分方案个数为? ? ? f(n，k-1)。
? ?
?状态转移方程：
?显然，求f(n，k)满足动态规划问题的最优性原理、无后效性和有重叠子问题性质。所以特别适合采用动态规划法求解。设置动态规划数组dp，用dp[n][k]存放f(n，k)。对应的完整程序如下：
int dp[MAXN][MAXN]; //动态规划数组
void Split(int n，int k) //求解算法
{ for (int i=1;i<=n;i++)
for (int j=1;j<=k;j++)
{ if (i==1 || j==1)
dp[i][j]=1;
else if (i<j)
dp[i][j]=dp[i][i];
else if (i==j)
dp[i][j]=dp[i][j-1]+1;
else
dp[i][j]=dp[i][j-1]+dp[i-j][j];
}
}
不知道别人怎么样，我对于这个问题的文字描述不太懂，后来我自己找了不少资料，这才有了自己的理解：
上面的状态转移方程f(n,k)我们可以看成把数字n分成最多k份的所有方案个数（注意是所有，即1~k份），对于这个状态转移方程，下面是我的理解：
（1）n=1或k=1：即把1分成k份，或者把n分成1份，其分法都只有一种
（2）n<k：把n分成k份，显然n最多分成n份，所以f(n,k)=f(n,n)
（3）n=k：把n分成k份，我们可以分为分成k份的和其他份数（1~k-1），分成k份只有一种，而分成其他份数的有f(n,k-1)，所以f(n,k)=f(n,k-1)+1
（4）n>k：把n分成k份，类似（3），我们把份数分为k份和其他份数（1~k-1），其他份数表示为：f(n,k-1)，而分成k份的因为必须分成k份，所以我们先每一份分1，还剩n-k，然后把n-k正常分成最多k份，表示为：f(n-k,k)，即f(n,k)=f(n,k-1)+f(n-k,k)
有的小伙伴可能不太理解为什么（3）和（4）都是同样的分法，为什么分成k份的在（3）只有1种，而在（4）中有f(n-k,k)种，这里我解释一下，在（3）中n=k，分成k份每一份为1，而在（4）中，分成k份，肯定存在有的一份大于1的，所以两者有区别。
还可能有像 “认为（4）中的f(n-k,k)应该是f(n,k)，因为要把n分成k份” ，实际上，如果这样认为，有一点没弄清楚，那就是f(n,k)的定义，f(n,k)是把数字n分成最多k份的所有方案个数（注意是所有，即1~k份），也就是既要分成k份还要分成k-1份,k-2份,k-3份,...,1份，所以，你懂了吗！