OpenJudge 4117 简单的整数划分问题对递推式的一些思考

ACM-ICPC

Publish Date: 2020-11-09

题目大意

把一个正整数分成任意个正整数的和（4=3+1,4=1+3被认为是一致的），请计算所有可能的划分数量。

思路

一直在想递推式，但是始终会出现重复的情况，找不到一种不会重复的情况。
~~直到比赛完之后~~
我们假定 f[x] 表示数值x可划分的情况，那么我们怎么从f[x-1] 递推过来呢？
如果只是单纯的把f[x-1]中的每一个情况的任意一个数加1，或者再添一个1的话，就会出现重复情况。比如：4=2+1+1，4=3+1，那么他们都能组成5=3+1+1。即使递推一次不相同，继续推下去，刚开始大不相同的数的划分方式，最终也有可能相同，所以结果就会错误。
不难发现，产生重复的原因是在于无法知道是把上一个情况的哪一个数加上一引起的。
而这个问题是有解决方法的，且有两种思考方式，而令我感到惊讶的是，这两种思路的递推式看起来竟然完全一致。

1.~~很容易~~想到：如果把每个数都加上一，那么就不会出现重复了。，那么我们可以令f[n][k]，为 把n分为小于等于 k 组 的方案数。
正推可能有点困难，所以不妨尝试反推：
新增一个新的组，但是什么也不放，那么就有：f[n][k+1]+=f[n][k]；往每一组都加一个1，则有f[n+k][k]+=f[n][k]。
可以发现，这两个操作就是所有的不会产生重复的操作了。（+2，+3的情况都会包涵在+1的情况中了）那么我们就能写出递推式了：f[n][k]=f[n][k-1]+f[n-k[[k]。

当然，还有很多细节没有处理：
f[n][m] (m>n) =f[n][n]。因为n个数最多放m组。
f[n][n]=1+f[n][n-1]。每组放一个为一种情况，其余情况肯定至少有一组没有放。(注意：f[n][n-1]所代表的含义等价于就是至少有一组没有放)

边界情况：f[n][1]=1;f[1][n]=1。
因为题目询问次数较少，直接递归就能写了。

2. 上一个思路是把每一组加一，还有一种思路是：既然重复是有一次次地加一造成的（因为每次加一可以让它到达每一个数，比如1到10，那么它可以遍历1到10之间每一个数，那么就可能产生重复）。
既然知道了问题的来源，那么我们就可以对每次加的数进行限制。
令f[n][k]表示把n分组，且里面最大的数不能超过k，的方案数。
那么不难发现，f[n][k]是由这两种分配方式组成的：有k的，没有k的。
那么就可以写出递推式了：f[n][k]=f[n][k-1]（不含有k的）+f[n-k][m]（既然包含k了，那么它的方案数显然等于 f[n-k][k]的方案数，因为把这种方案补上一个k，就是f[n][k]的方案数了）。

那么细节也好处理了：
f[n][m]（m>n）=f[n][n]（n不可能被比它大的数表示）
f[n][n] = 1+f[n][n-1] （n被n表示，除此之外，其他方式必定所有数小于n）
边界情况：
f[1][n]=1（只有一个1）;f[n][1]=1（全是1）;

然后，会发现，递推式真的是完全一致！！！
代码也是完全一致！！！
但是思路确实截然不同。

~~数学真tm的有趣啊（全恼）~~

代码

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

int n;

inline int calc(int n,int m)
{
    if(n==1||m==1) return 1;
    if(n<=m) return 1+calc(n,n-1);//把两种情况写道一块了
    return calc(n,m-1)+calc(n-m,m);
}

int main()
{
    while(~scanf("%d",&n))
        printf("%d\n",calc(n,n));
    return 0;
}