大家可能會(huì)想：正整數(shù)拆分誰不會(huì)啊，2年級(jí)就會(huì)了，為啥要學(xué)啊

例題

正整數(shù)拆分有好幾種，這里我們列舉兩種講。

關(guān)系

我們看著第一幅圖，頭向左轉(zhuǎn)90°，記住你看到的圖，再來看第二幅圖，你會(huì)驚奇的發(fā)現(xiàn)：第一幅圖向左轉(zhuǎn)90°就變成了第二幅圖！因此，我們做出來一道題，就能推出另外一題。這種情況我們稱之為Ferrers圖

例2

我們先思考狀態(tài)定義：f[i][j]表示把i恰好分成j個(gè)正整數(shù)的方案數(shù)

后面考慮狀態(tài)轉(zhuǎn)移方程，第一步先列表格。

?我相信聰明的你們已經(jīng)發(fā)現(xiàn)了規(guī)律：f[9][4]=1+2+2+1（i=5那行）f[8][3]=1+2+1（i=5那行的前4個(gè)）

后面，我們用數(shù)學(xué)方法推導(dǎo)一下規(guī)律：

?因此得到狀態(tài)轉(zhuǎn)移方程：f[i][j]=f[i-j][1]+f[i-j][2]+……+f[i-j][j]，但是時(shí)間復(fù)雜度為O(n^3)。于是我們進(jìn)行優(yōu)化。

我們看到f[i-j][1]+f[i-j][2]+……+f[i-j][j-1]=f[i-1][j-1]，為什么因?yàn)楦鶕?jù)前面的狀態(tài)轉(zhuǎn)移方程，f[i-1][j-1]等于f[i-j][1]+f[i-j][2]+……+f[i-j][j-1]。最后，我們的狀態(tài)轉(zhuǎn)移方程變?yōu)閒[i][j]=f[i-1][j-1]+f[i-j][j]！

最后給個(gè)代碼，

cin>>n>>m;
for(int i=1;i<=n;i++) f[i][1]=1;
for(int j=2;j<=m;j++)for(int i=j;i<=n;i++)f[i][j]=f[i-1][j-1]+f[i-j][j];
cout<<f[n][n]<<endl;

變種

太戈編程習(xí)題

456. 數(shù)的劃分

題目描述

將整數(shù)n分成k份，且每份不能為空。任意兩個(gè)方案不能相同(不考慮順序)。 例如：n=7，k=3，下面三種分法被認(rèn)為是相同的。 1,1,5;1,5,1;5,1,1; 問有多少種不同的分法。

#include <bits/stdc++.h>
using namespace std;
#define N 210
#define K 16
int n,k,f[N][K];
int main(){freopen("partition.in","r",stdin);freopen("partition.out","w",stdout);cin>>n>>k;for(int i=1;i<=n;i++) f[i][1]=1;for(int j=2;j<=k;j++)for(int i=j;i<=n;i++)f[i][j]=f[i-1][j-1]+f[i-j][j];cout<<f[n][k]<<endl;return 0;
}

457. 訓(xùn)練計(jì)劃

題目描述

要想成為編程高手，必須獨(dú)立編程n個(gè)小時(shí)。作為編程教練，你希望為孩子們?cè)O(shè)計(jì)一套訓(xùn)練計(jì)劃，將n個(gè)小時(shí)拆分成若干天完成。已知每天最多安排不能超過k小時(shí)，你的訓(xùn)練計(jì)劃要求每天的訓(xùn)練量不能出現(xiàn)下降。請(qǐng)問一共有多少種訓(xùn)練方案？

?

#include <bits/stdc++.h>
using namespace std;
#define N 350
#define K 34
long long n,k,f[N][K];
int main(){freopen("training.in","r",stdin);freopen("training.out","w",stdout);cin>>n>>k;for(long long i=1;i<=n;i++) f[i][1]=1;for(long long j=2;j<=k;j++)for(long long i=j;i<=n;i++)f[i][j]=f[i-1][j-1]+f[i-j][j];long long ans=0;for(long long i=1;i<=k;i++)ans+=f[n][i];cout<<ans<<endl;return 0;
}

?希望大家可以點(diǎn)個(gè)贊、關(guān)個(gè)住，謝謝o(*^＠^*)o