【題意】將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; } View Code

?

總結一下幾種情況：

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。

轉載于:https://www.cnblogs.com/onioncyc/p/6295938.html

總結

以上是生活随笔為你收集整理的【51NOD】1201 整数划分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。