NOIP 提高 2017 第一轮 第 23 题：递归计算整数拆分数

题目

```
#include <iostream> 
using namespace std;   
int g(int m, int n, int x)   
{     
    int ans = 0;   
    int i;   
    if (n == 1)  
        return 1;     
    for (i = x; i <= m / n; i++)         
        ans += g(m - i, n - 1, i);     
    return ans; 
} 
int main() 
{     
    int t, m, n;     
    cin >> m >> n;    
    cout << g(m, n, 0) << endl;     
    return 0;   
} 
```
输入：8 4   
输出：_________

请写出程序的输出结果。

答案

15

题解

考点定位

非递减非负整数拆分的递归计数。

解题过程

输入 8 4，调用 g(8,4,0)，统计四个非递减非负整数之和为 8 的方案。首项最多为 8/4=2。

• 首项为 0：剩余三个非递减非负整数之和为 8。第二项分别为 0、1、2 时，有 5、3、2 种，共 10 种。
• 首项为 1：合法方案为 (1,1,1,5)、(1,1,2,4)、(1,1,3,3)、(1,2,2,3)，共 4 种。
• 首项为 2：只能是 (2,2,2,2)，共 1 种。

总数为 10+4+1=15。

答案：15。

易错提醒

初始 x=0，允许取 0；递归把当前 i 作为下界，允许相邻项相等。