用递归实现整数拆分

题目：

题目分析：

将给定整数n无序拆分成最大数为k的拆分数，求拆分方案个数

如当n=4，k=1时仅有一种拆分方法：4=1+1+1+1；

当n=4，k=2时有：

4=1+1+1+1；

4=1+1+2；

4=2+2；

这三种拆分方法，如果n=4，k=3呢？

可以看到当n相同时，k较小的拆分方法必然包含于k较大的拆分方法当中；

那我们定义一个函数f（n，k），这个函数可以得到将n无序拆分成最大数为k的拆分数的方案个数；

又因为当n=1或者k=1时f（n，k）的值必定为1（n=1时只有1=1这一种拆分方法，k=1的话就不用讲了吧）

又f（n，k）>=f(n,k-1);令f(n,k)-f(n,k-1)=t;那么我们想知道f(n,k)的值，就只要把t求出来再让它和f(n,k-1)相加就可以啦；

至于f(n,k-1)是多少......那就让f(n,k-2)去和对应的t值去相加！！这就交给电脑去完成就好啦，我们要做的就是求出t的值，那么t等于多少呢？

再观察一下n=4，k=2和n=4，k=1；

可以发现，k=2比k=1多出来的两项就是：

4=1+1+2和4=2+2；拆分出来的数当中必定含有（+2）这一项，那如果我把等式两边都减掉2呢，就变成了：

2=1+1和2=2；这刚刚好就是n=2，k=2的情况；即f(n,k)比f(n,k-1)多出来的拆分方法数就是f(n-k,k);

简单点理解就是f(n,k)比f(n,k-1)多出来的拆分方法必定都包含有k这一项，那把多出来的这些拆分方法等式两边都减掉k的话就得到了f(n-k,k)对应的拆分方法。

所以我们f(n,k)-f(n,k-1)=t;中的这个t的值就是f(n-k,k),由此我们就可以把实现f(n,k)功能的代码写出来啦：

代码实现：

#include <stdio.h>
int f(int n,int k){
if(k==1||n==1)return 1;
if(n<0)return 0;//因为t=f(n-k,k)防止出现k>n的情况导致错误
int t=f(n-k,k);
return t+f(n,k-1);
}
int main(){
int n,k;
while(scanf("%d,%d",&n,&k)!=EOF)//当输入文件结束符时结束循环
printf("%d\n",f(n,k));
}

这样就用递归实现了整数拆分啦，但是当数据较多而且数值较大的时候，使用递归就会导致大量的重复计算，在这样的情况下就会运行超时，如图：

 如何解决这个问题呢，这里用到动态规划的方法：

即我们设定一个数组，dp[101][101];

当我们算出f(4,4)=5之后就直接把这个数字存入dp[4][4];

下次遇到要求这个的值就直接从数组中拿而不用再进行一次运算了；

代码实现如下：

#include <stdio.h>
int dp[102][102]={0};//将整个数组初始化为0,用于判断dp[n][k]是否有被赋值
int f(int n,int k){
if(k==1||n==1)return 1;
if(n<0)return 0;//因为t=f(n-k,k)防止出现k>n的情况导致错误
int t;
if(n>k&&dp[n-k][k]!=0)t=dp[n-k][k];//如果dp[n-k][k]已经被赋值就可以直接使用
else t=f(n-k,k);//否则就计算f(n-k,k);
if(dp[n][k-1]!=0)dp[n][k]=t+dp[n][k-1];
else dp[n][k]=t+f(n,k-1);//给dp[n][k]赋值；
return dp[n][k];
}
int main(){
int n,k;
while(scanf("%d,%d",&n,&k)!=EOF)//当输入文件结束符时结束循环
printf("%d\n",f(n,k));
}

结果如图：

 可以看到这样的方法非常的快啊！！3ms就完成了，太棒啦！