這一題實際上是組合數學里面的經典問題，跟第二類Stirling數有些相似。可以把一個數值為n的數看成n個小球，劃分的份數k看作是k個盒子，那么本題的要求就是：
將n個小球放到k個盒子中，小球之間與盒子之間沒有區別，并且最后的結果不允許空盒
與第二類Stirling數的遞推公式的推導過程相似：
將n個小球放到k個盒子中的情況總數 =?
1. 至少有一個盒子只有一個小球的情況數
+
2. 沒有一個盒子只有一個小球的情況數
?
這樣進行劃分的原因是這種分類足夠特殊，1和2都有可以寫出來的表達式：
1. 因為盒子不加區分，那么1的情況數與“將n-1個小球放到k-1個盒子中”的情況數一樣
2. 沒有一個盒子只有一個小球，那么把每個盒子中拿出來一個小球，對應的是“把(n-k)個小球放到k個盒子中的情況數”
至于1和2中的兩種等價關系為什么成立，可以用集合A=集合B的方式去證明
?
最后將上面的敘述轉化為dp的表達形式：
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，加我一起討論問題，一起進步^-^
)
