【题意】将n划分成不同正整数的和的方案数。
【算法】动态规划
【题解】
暴力：f[i][j]:只用前1..i的数字，总和为j的方案数
本质上是01背包，前i个物体，总质量为j的方案数
f[i][j]=f[i-1][j]+f[i-1][j-i]
复杂度O(n^2)
优化：
我们发现，因为要求数字不同，那么数字最多也小于sqrt(n*2)个。
极端情况：1+2+3+...+mx=n mx<sqrt(n*2)
所以可以改一下状态的设计
f[i][j]:用了i个数字，总和为j的方案数。
转移状态：
①如果i个数里没有1：那么把i个数字都-1，就对应“取了i个数字，总和为j-i”的，i个数都+1
②i个数字里有1：对应"取了i-1个数字，总和为j-i"的情况，再加一个新的数字1，其他i-1个数也都+1啊
f[i][j]=f[i-1][j-i]+f[i][j-i]
初始状态f[0][0]=1
#include<cstdio> #include<algorithm> using namespace std; const int maxn=50010; const long long MOD=1000000007; int f[350][maxn],n; int main() { scanf("%d",&n); f[0][0]=1; for(int i=1;i*i<=n*2;i++) for(int j=1;j<=n;j++) if(j-i>=0)f[i][j]=(f[i-1][j-i]+f[i][j-i])%MOD; long long ans=0; for(int i=1;i*i<=n*2;i++) ans=(ans+f[i][n])%MOD; printf("%lld",ans); return 0; }
总结一下几种情况：
1.$f_{n,m}$表示将数字n分成m个非负整数的方案。
$$f_{i,j}=f_{i,j-1}+f_{i-j,j}$$
如果方案中有0就去掉，否则整体-1。
2.$f_{n,m}$表示将数字n分成m个正整数的方案。
$$f_{i,j}=f_{i-1,j-1}+f_{i-j,j}$$
如果方案中有1就去掉，否则整体-1。
3.$f_{n,m}$表示将数字n分成m个不同正整数的方案数。
$$f_{i,j}=f_{i-j,j-1}+f_{i-j,j}$$
强制递增，如果方案第一位是1那么去掉后整体-1，否则整体-1。