這一題實際上是組合數(shù)學(xué)里面的經(jīng)典問題，跟第二類Stirling數(shù)有些相似。可以把一個數(shù)值為n的數(shù)看成n個小球，劃分的份數(shù)k看作是k個盒子，那么本題的要求就是：

將n個小球放到k個盒子中，小球之間與盒子之間沒有區(qū)別，并且最后的結(jié)果不允許空盒

與第二類Stirling數(shù)的遞推公式的推導(dǎo)過程相似：

將n個小球放到k個盒子中的情況總數(shù) =?

1. 至少有一個盒子只有一個小球的情況數(shù)

+

2. 沒有一個盒子只有一個小球的情況數(shù)

?

這樣進(jìn)行劃分的原因是這種分類足夠特殊，1和2都有可以寫出來的表達(dá)式：

1. 因為盒子不加區(qū)分，那么1的情況數(shù)與“將n-1個小球放到k-1個盒子中”的情況數(shù)一樣

2. 沒有一個盒子只有一個小球，那么把每個盒子中拿出來一個小球，對應(yīng)的是“把(n-k)個小球放到k個盒子中的情況數(shù)”

至于1和2中的兩種等價關(guān)系為什么成立，可以用集合A=集合B的方式去證明

?

最后將上面的敘述轉(zhuǎn)化為dp的表達(dá)形式：

f[n][k]代表將n個小球放到k個盒子中且沒有空盒的情況，那么

f[n][k] = f[n-1][k-1] + f[n-k][k]

?

這道題說是dp，其實就是遞推

代碼：

varf:array[0..1000,0..1000] of longint;m,n,i,j,k,l,ans:longint;beginreadln(n,k);for i:=1 to n dofor j:=1 to i dobeginf[i][j]:=f[i-j][j]+f[i-1][j-1];if (i=1) and (j=1) then f[i][j]:=1;end;writeln(f[n,k]);end.

?

?喜歡就收藏一下，vic私人qq：1064864324，加我一起討論問題，一起進(jìn)步^-^

轉(zhuǎn)載于:https://www.cnblogs.com/victorslave/p/4817687.html

總結(jié)

以上是生活随笔為你收集整理的[codevs1039]数的划分的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。