100 #P1505. *【动态规划:状态设计DP】数的划分[NOIP提高组2001]

*【动态规划:状态设计DP】数的划分[NOIP提高组2001]

对比:(1383: 【递归(难度:4)】加法分解方案3),20230819由scy加强数据

【题意】

将整数 nn 分成 kk 份,且每份不能为空,任意两种分法不能相同(不考虑顺序)。

例如: n=7,k=3n=7,k=3下面三种分法被认为是相同的。

1,1,5
1,5,1
5,1,1

问有多少种不同的分法。

【输入格式】

两个整数 n,k (6<n1000,2k10)n,k \ (6 < n \le 1000, 2 \le k \le 10)

【输出格式】

一个整数,即不同的分法。

7 3
4

【数据解释】

4种分法为:

1,1,5  
1,2,4   
1,3,3  
2,2,3