P1025 数的划分

May 5, 2026 · 4 分钟阅读 · 动态规划 ·

文章目录

题目信息

字段	内容
题号	P1025
难度	橙题（普及+）
知识点	递归、动态规划、整数划分

题目描述

将整数 n 分成 k 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

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

(1,1,5) (1,5,1) (5,1,1)

问有多少种不同的分法。

输入格式

一行两个正整数 n, k（6 < n ≤ 200, 2 ≤ k ≤ 6）。

输出格式

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

样例

输入

7 3

输出

解释：7 分成 3 份共有 4 种分法：1,1,5、1,2,4、1,3,3、2,2,3。

解题思路

核心思想

本题要求将 n 个相同的苹果放到 k 个不同的盘子中，每个盘子至少一个苹果，且不计顺序。这等价于求整数 n 的 k 部分无序拆分数。

核心递推思路基于对最大划分部分的讨论：

定义 f(m, n) 表示将整数 m 划分为不超过 n 个正整数之和的方案数（即每份最多为 n），则有：

f(m, n) = f(m, n-1) + f(m-n, n)

含义是：

f(m, n-1)：所有划分中不出现 n 的方案，等价于最大部分 ≤ n-1
f(m-n, n)：所有划分中至少出现一个 n 的方案，减去一个 n 后变成将 m-n 划分为最大部分 ≤ n 的问题

与原问题的联系：将 n 分成恰好 k 份 → 先给每份放 1 个苹果（保证非空），剩下 n-k 个苹果随意分配到 k 份中（允许某些份不再增加）。这就是为什么代码中调用的是 f(apple - plate, plate)。

递归边界

条件	返回值	含义
`m = 0`	`1`	恰好分完，是一种合法方案
`n = 1`	`1`	所有划分中最大部分不超过 `1`，只有全 `1` 这一种方案
`m < n`	`f(m, m)`	要划分的数比上限还小，上限缩小到 `m`

完整代码

C++

#include <iostream>
using namespace std;

int apple, plate;

// f(m, n): 将整数 m 划分为最大部分不超过 n 的方案数
int f(int m, int n) {
    if (m == 0 || n == 1) return 1;  // 边界：恰好分完 或 只能放 1
    if (m < n) return f(m, m);        // 上限大于剩余数，缩小上限
    return f(m - n, n) + f(m, n - 1); // 转移：包含 n + 不包含 n
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> apple >> plate;
    // 先给每份放 1 个苹果，再对剩余 apple-plate 个苹果做无限制划分
    cout << f(apple - plate, plate) << "\n";
    return 0;
}

关键代码讲解

为什么是 `f(apple - plate, plate)` 而不是 `f(apple, plate)`？

题目要求每份至少一个，等价于"先给 k 个盘子各放 1 个苹果，再将剩下的 n-k 个苹果任意分配"。所以实际要划分的数量是 n - k，而非 n。

理解递归转移

以 n = 7, k = 3 为例，实际调用 f(4, 3)：

f(4, 3) = f(4, 2) + f(1, 3)
         = [f(4,1) + f(2,2)] + [f(1,1)]
         = [1 + (f(0,2) + f(2,1))] + [1]
         = [1 + (1 + 1)] + 1
         = 4

对应 4 种分法：1+1+5, 1+2+4, 1+3+3, 2+2+3（加上每份固定的 1，即还原为原问题的分法）。

复杂度分析

方法	时间复杂度	空间复杂度
递归（无记忆化）	`O(2^n)`	`O(n)`（递归栈）

本题数据范围 n ≤ 200，纯递归会有大量重复计算。可以通过记忆化搜索将时间优化到 O(n * k)，也可以转化为二维动态规划。

记忆化优化版本

#include <iostream>
#include <cstring>
using namespace std;

int apple, plate;
int memo[205][205];

int f(int m, int n) {
    if (m == 0 || n == 1) return 1;
    if (m < n) return f(m, m);
    if (memo[m][n] != -1) return memo[m][n];
    return memo[m][n] = f(m - n, n) + f(m, n - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> apple >> plate;
    memset(memo, -1, sizeof(memo));
    cout << f(apple - plate, plate) << "\n";
    return 0;
}

记忆化后时间复杂度优化为 O(n * k)，空间复杂度 O(n * k)。

易错点

不要直接调用 f(apple, plate)：这样计算的是"将 n 分成最大不超过 k 份"，允许某些份为 0，与题意不符。
递归深度：本题 n ≤ 200，递归深度不会超过 200，不会栈溢出。但如果数据范围更大，建议改用递推（动态规划）。
数据类型：当 n = 200, k = 6 时答案较大但不会超过 int 范围，无需使用 long long。

其他语言解法

Python

import sys
sys.setrecursionlimit(10000)

def f(m: int, n: int) -> int:
    """将 m 划分为最大部分不超过 n 的方案数"""
    if m == 0 or n == 1:
        return 1
    if m < n:
        return f(m, m)
    return f(m - n, n) + f(m, n - 1)

if __name__ == "__main__":
    apple, plate = map(int, sys.stdin.readline().split())
    print(f(apple - plate, plate))

Java

import java.io.BufferedInputStream;
import java.io.InputStream;
import java.util.Arrays;

public class Main {
    static int[][] memo = new int[205][205];

    static int f(int m, int n) {
        if (m == 0 || n == 1) return 1;
        if (m < n) return f(m, m);
        if (memo[m][n] != -1) return memo[m][n];
        return memo[m][n] = f(m - n, n) + f(m, n - 1);
    }

    public static void main(String[] args) {
        InputStream in = new BufferedInputStream(System.in);
        int apple = nextInt(in), plate = nextInt(in);
        for (int[] row : memo) Arrays.fill(row, -1);
        System.out.println(f(apple - plate, plate));
    }

    static int nextInt(InputStream in) {
        int c, val = 0;
        try {
            while ((c = in.read()) <= 32) {}
            do { val = val * 10 + (c - '0'); } while ((c = in.read()) > 32);
        } catch (Exception e) {}
        return val;
    }
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

var memo [205][205]int

func f(m, n int) int {
	if m == 0 || n == 1 {
		return 1
	}
	if m < n {
		return f(m, m)
	}
	if memo[m][n] != -1 {
		return memo[m][n]
	}
	memo[m][n] = f(m-n, n) + f(m, n-1)
	return memo[m][n]
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var apple, plate int
	fmt.Fscan(reader, &apple, &plate)
	for i := range memo {
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}
	fmt.Println(f(apple-plate, plate))
}

JavaScript

'use strict';

const memo = Array.from({ length: 205 }, () => new Int32Array(205).fill(-1));

function f(m, n) {
    if (m === 0 || n === 1) return 1;
    if (m < n) return f(m, m);
    if (memo[m][n] !== -1) return memo[m][n];
    return memo[m][n] = f(m - n, n) + f(m, n - 1);
}

const [apple, plate] = require('fs')
    .readFileSync('/dev/stdin', 'utf8')
    .trim()
    .split(' ')
    .map(Number);

console.log(f(apple - plate, plate));