整数拆分问题的动态规划解法

输入n，和k，问将n用1到k这k个数字进行拆分，有多少种拆分方法。例如：n=5,k=3 则有n=3+2, n=3+1+1, n=2+1+1+1, n=2+2+1, n=1+1+1+1+1这5种拆分方法。

这个题目是个比较明显的动态规划，如果想不到是背包问题，也可以写出状态转移方程如下。

用a[i][j]表示考虑到用数j进行拼接时数字i的拼接方法，可以得到状态转移方程如下：a[i][j]=a[i][j-1]+a[i-j][j-1]+a[i-2j][j-1]+a[i-3j][j-1]…+a[0][j-1]意思很明显，就将j-1状态可以到达a[i][j]的状态的数字相加。由于得到的结果可能相当大，已经超过了long long，所以应该用大数。但是若跑完所有数据，用大数会超过一秒，我们通过大数的程序可以达到，最大的数字为33位，那么，我们可以将两个long long的数字进行拼接，组成一个超过33位的数。这样增加了速度，这种比较慢的算法也可以不超时。

view sourceprint?01 #include <iostream> 

02 #include<cstdio> 

03 using namespace std; 

04   

05 long long a[1200][200]={0},b[1200][120]={0}; 

06   

07 int main() 

08 { 

09     int i,j,n,m,k; 

10     long long inf,x; 

11     inf=1; 

12     for(i=0;i<18;i++) 

13     { 

14         inf=inf*10; 

15     } 

16     cin>>n>>m; 

17     for(i=1;i<=n;i++) 

18     { 

19         b[i][1]=0; 

20         a[i][1]=1; 

21         for(j=2;j<=m;j++) 

22         { 

23             if(j>i) 

24             { 

25                 a[i][j]=a[i][j-1]; 

26                 b[i][j]=b[i][j-1]; 

27                 continue; 

28             } 

29             a[i][j]=a[i][j-1]; 

30             b[i][j]=b[i][j-1]; 

31             for(k=1;k*j<=i;k++) 

32             { 

33                 if(i-j*k==0) 

34                 { 

35                     a[i][j]++; 

36                     b[i][j]+=a[i][j]/inf; 

37                     a[i][j]=a[i][j]%inf; 

38                 } 

39                 else { 

40                     b[i][j]+=b[i-j*k][j-1]; 

41                     a[i][j]+=a[i-j*k][j-1]; 

42                     b[i][j]+=a[i][j]/inf; 

43                     a[i][j]=a[i][j]%inf; 

44                 } 

45             } 

46         } 

47     } 

48     if(b[n][m]!=0) 

49     { 

50         cout<<b[n][m]; 

51     } 

52     cout<<a[n][m]<<endl; 

53     return 0; 

54 }

其实这个题有更快的方法，看上面这个式子a[i][j]=a[i][j-1]+a[i-j][j-1]+a[i-2j][j-1]+a[i-3j][j-1]…+a[0][j-1]我们可以发现，其实可以转到a[i][j]的状态有两种，一种是a[i][j-1]就是不用j这个数字拼接i这个数字的方法数，另一种是a[i-j][j]就是用了j这个数字拼接的到i-j的方法数那么状态转移方程就可以写成a[i][j]=a[i][j-1]+a[i-j][j]不用加那么多项，就降低了一个数量级的复杂度，仍然利用上面处理大数的方法。

view sourceprint?01 #include <iostream> 

02 #include <cstdio> 

03 #include <cstring> 

04 using namespace std; 

05   

06 long long a[1100][110],b[1100][110],inf; 

07   

08 int main(){ 

09     int n,k,i,j; 

10     for(inf=1,i=0;i<18;i++) inf*=10; 

11     memset(a,0,sizeof(a)); 

12     memset(b,0,sizeof(b)); 

13     scanf("%d%d",&n,&k); 

14     for(i=0;i<=k;i++) a[0][i]=1; 

15     for(i=1;i<=k;i++){ 

16         for(j=1;j<=n;j++){ 

17             if(j-i<0){ 

18                 b[j][i]=b[j][i-1]; 

19                 a[j][i]=a[j][i-1]; 

20                 continue; 

21             } 

22             b[j][i]=b[j][i-1]+b[j-i][i]+(a[j][i-1]+a[j-i][i])/inf; 

23             a[j][i]=(a[j][i-1]+a[j-i][i])%inf; 

24         } 

25     } 

26     if(b[n][k]) printf("%I64d",b[n][k]); 

27     printf("%I64d\n",a[n][k]); 

28     return 0; 

29 }

其实我们还可以在空间上进行优化，看这个式子a[i][j]=a[i][j-1]+a[i-j][j]我们发现，如果外层循环式j实际上是上一次j在i的值，加上这次j在i-j的值，那么可以只开一维数组，代码如下：

view sourceprint?01 #include <iostream> 

02 #include <cstdio> 

03 #include <cstring> 

04 using namespace std; 

05   

06 long long a[1100],b[1100],inf; 

07   

08 int main(){ 

09     int n,k,i,j; 

10     for(inf=1,i=0;i<18;i++) inf*=10; 

11     scanf("%d%d",&n,&k); 

12     memset(a,0,sizeof(a)); 

13     memset(b,0,sizeof(b)); 

14     a[0]=1; 

15     for(i=1;i<=k;i++){ 

16         for(j=1;j<=n;j++){ 

17             if(j-i<0) continue; 

18             b[j]=b[j]+b[j-i]+(a[j]+a[j-i])/inf; 

19             a[j]=(a[j]+a[j-i])%inf; 

20         } 

21     } 

22     if(b[n]) printf("%I64d",b[n]); 

23     printf("%I64d\n",a[n]); 

24     return 0; 

25 }

这实际上是完全背包问题，只是状态转移方程形式有所不同，不过状态转移的方向是完全相同的。for(j=1;j<=k;j++) for(i=1;i<=n;i++) a[i]=a[i]+a[i-j]，是这个题目的方法，由于i是从前往后的，那么a[i]前面的a[i-j]已经是已经考虑了j，而如果是for(j=1;j<=k;j++) for(i=n;i>=1;i--) a[i]=a[i]+a[i-j] ;i是从后往前的，那么a[i-j]是没考虑j的，正是一个只能用一次的情形。

此题目是单组测试数据，那么有两种情况，一种是题目没说清楚，实际上是多组（这种情况只能试），一种是真正的单组，但是测试数据的文件特别多。这种情况每个文件会单独跑一次数据，多个文件加起来的时间就是你做这个题用的时间。如果是多组数据，我们一般喜欢打表，但是对于真正的单组数据，打表则是下下策，因为每跑一次就打一遍所有的表，很浪费时间。所以只跑出输入数据需要的结果即可，对于这个题目的第一种解法，如果打表的话，就只能TLE，所以以后遇到真正的单组，一定要注意这个问题。

另外一个需要注意的是关于64位整数的，64位整数的申明可以有__int64和long long两种，编译器都支持，但是对于有些OJ只支持long long，输入输出上可以”%I64d”也可以”%lld”对于Mingw和CodeBlocks只能用%I64d但是，对于有些OJ则只能用%lld，所以比赛之前务必把这个搞清楚。当然，cin和cout就不用考虑这么多了，但是会相对慢些。