思路

我们可以使用动态规划来解决此问题。下面是详细的思考过程。

1. 定义状态 我们定义一个数组 $dp$，其中 $dp[i]$ 表示正整数 $i$ 有多少种不同的划分方案。我们的最终目标是求出 $dp[n]$。

2. 状态转移方程 为了计算 $dp[i]$，我们可以考虑构成整数 $i$ 的划分中，最后一个加数是什么。这个加数可以是 $1, 2, 3, \ldots, i$ 中的任意一个。

   • 如果最后一个加数是 $1$，那么它前面的所有加数之和必须为 $i-1$。这部分的划分方案数就是 $dp[i-1]$。
   • 如果最后一个加数是 $2$，那么它前面的所有加数之和必须为 $i-2$。这部分的划分方案数就是 $dp[i-2]$。
   • 如果最后一个加数是 $j$，那么它前面的所有加数之和必须为 $i-j$。这部分的划分方案数就是 $dp[i-j]$。
   • ...
   • 如果最后一个加数是 $i$，那么这个划分就只有 $i$ 本身。它前面的加数之和为 $0$。这部分的划分方案数记为 $dp[i]$。

   将以上所有情况相加，我们就得到了 $dp[i]$ 的总方案数。因此，状态转移方程为： $dp[i]$ = $dp[i-1]$ + $dp[i-2]$ + $\cdots$ + $dp[n-1]$ + $dp[n]$ 或者写作求和形式： $dp[i] = \sum_{j=1}^{i} dp[i-j]$

3. 初始化（边界条件） 根据状态转移方程，我们需要一个初始值。我们定义 $dp[0] = 1$。这看起来可能不直观，但它是有意义的：$dp[0]=1$ 表示 "和为0" 只有一种方案，即 "什么都不加"（空集）。这个定义是必要的，例如在计算 $dp[i]$ 时，当最后一个加数是 $i$ 本身时，前面的和为 $i-i=0$，这对应了 $dp[i]$ 的一种方案。

4. 计算顺序 我们从小到大依次计算 $dp[1], dp[2], \ldots, dp[n]$。

C++ 代码

#include <iostream>
#include <vector>

int main() {
    // 读取输入的正整数n
    int n;
    std::cin >> n;

    if (n == 0) {
        std::cout << 0 << std::endl;
        return 0;
    }

    // 定义dp数组，大小为n+1，用于存储dp[0]到dp[n]
    // 使用long long防止数据溢出
    std::vector<long long> dp(n + 1, 0);

    // 初始化边界条件
    // dp[0]=1 表示和为0只有一种方案（空集）
    dp[0] = 1;

    // 循环计算dp[1]到dp[n]
    for (int i = 1; i <= n; ++i) {
        // 根据状态转移方程 dp[i] = sum(dp[i-j]) for j=1 to i
        for (int j = 1; j <= i; ++j) {
            dp[i] += dp[i - j];
        }
    }

    // 输出最终结果
    std::cout << dp[n] << std::endl;

    return 0;
}

Python 代码

try:
    # 读取输入的正整数n
    n_str = input()
    n = int(n_str)
    
    if n == 0:
        print(0)
    else:
        # 初始化dp列表，大小为n+1，所有元素初始化为0
        dp = [0] * (n + 1)
        
        # 设置边界条件
        # dp[0]=1 表示和为0只有一种方案（空集）
        dp[0] = 1
        
        # 从1到n遍历，填充dp列表
        for i in range(1, n + 1):
            # 根据状态转移方程 dp[i] = sum(dp[i-j]) for j=1 to i
            for j in range(1, i + 1):
                dp[i] += dp[i - j]
        
        # 输出最终结果
        # Python的整数可以自动处理大数，无需担心溢出
        print(dp[n])

except (ValueError, IndexError):
    print("无效输入")

Java 代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入的正整数n
        int n = scanner.nextInt();
        
        if (n == 0) {
            System.out.println(0);
            scanner.close();
            return;
        }
        
        // 定义dp数组，大小为n+1
        // 使用long类型防止数据溢出，因为结果会很大
        long[] dp = new long[n + 1];
        
        // 初始化边界条件
        // dp[0]=1 表示和为0只有一种方案（空集）
        dp[0] = 1;
        
        // 循环计算dp[1]到dp[n]
        for (int i = 1; i <= n; i++) {
            // 根据状态转移方程 dp[i] = sum(dp[i-j]) for j=1 to i
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[i - j];
            }
        }
        
        // 输出最终结果
        System.out.println(dp[n]);
        
        scanner.close();
    }
}

题目描述

一个正整数$n$可以表示成若干个正整数之和，形如:$n$ = $a_1$ + $a_2$ + $\cdots$ + $a_k$，其中$a_1$, $a_2$, $\ldots$, $a_k$是正整数，且不考虑加数的顺序（即顺序不同但组合相同视为同一种划分）。

这样的表示称为正整数$n$的一种划分。

现在给定一个正整数$n$，请求出 $n$ 有多少种不同的划分方案，并输出方案数。

输入

共一行，包含一个整数$n$。

输出

共一行，包含一个整数，表示总划分数量。

示例1

输入：

3

输出：

4

提示

对于$n = 3$，划分方案有：

• $3$
• $2 + 1$
• $1 + 2$
• $1 + 1 + 1$

示例2

输入：

4

输出：

8

提示

对于$n = 4$，划分方案有：

• $4$
• $3 + 1$
• $1 + 3$
• $2 + 2$
• $1 + 1 + 2$
• $2 + 1 + 1$
• $1 + 2 + 1$
• $1 + 1 + 1 + 1$